퇴사


백준 [14501] 퇴사

문제보기
Alt text

풀이

  • 백트래킹

소스코드

import java.util.Scanner;

public class Main {
	static int N, ans;
	static int[][] schedule;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		ans = 0;
		schedule = new int[N][2];

		for (int i = 0; i < N; i++) {
			schedule[i][0] = sc.nextInt();
			schedule[i][1] = sc.nextInt();
		}

		work(new boolean[N], 0, 0);
		System.out.println(ans);
	}

	public static void work(boolean[] isOk, int price, int idx) {
		if (idx >= N) {
			ans = Math.max(price, ans);
			return;
		}

		for (int i = idx; i < N; i++) {
			if (isOk[i])
				continue;
			if (!isOk[i] && i + schedule[i][0] > N) {
				idx++;
				work(isOk, price, idx);
				continue;
			}
			int memo = idx;
			price += schedule[i][1];
			for (int j = i; j < i + schedule[i][0]; j++) {
				isOk[j] = true;
			}
			idx = i + schedule[i][0];

			work(isOk, price, idx);

			price -= schedule[i][1];
			for (int j = i; j < i + schedule[i][0]; j++) {
				isOk[j] = false;
			}
			idx = memo;
		}
	}
}