[백준] 14501 : 퇴사

문제

https://www.acmicpc.net/problem/14501

 

 

입출력

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

45

 

---

아이디어

 

1) 백트래킹

n이 최대 15이므로  선택 O, 선택 X

 

2) DP

dp[i] // i번째 상담 결정시 최대 수익 (뒤부터)

상담 O dp[i + T[i]] + P[i]

상담 X dp[i + 1] 

 

코드 

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N; // 내림차순 순서, 어떤 순서로 서 있는지
	static int[] times;
	static int[] prices;
	static boolean[] visited;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		times = new int[N];
		prices = new int[N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			times[i] = Integer.parseInt(st.nextToken());
			prices[i] = Integer.parseInt(st.nextToken());
		}
		back(0, 0);
		System.out.println(max);
	}

	static int max = 0;

	static void back(int t, int p) {
		if (t >= N) {
			max = Math.max(max, p);
			return;
		}
		if (t + times[t] <= N) {
			back(t + times[t], p + prices[t]);
		}
		back(t + 1, p);

	}

}

int[] dp = new int[N + 1]; // i번째 상담 결정시 최대 수익 (뒤부터...)
    for (int n = N - 1; n >= 0; n--) {
        dp[n] = dp[n + 1]; // 상담 x
        if (n + times[n] <= N) {
            dp[n] = Math.max(dp[n + times[n]] + prices[n], dp[n]);
        }
    }
System.out.println(dp[0]);