백준 [14501] 퇴사
문제보기
풀이
소스코드
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;
}
}
}