디피는 개날먹이다

boj 14501 퇴사

백트랙킹으로 쉽게 풀 수 있다

Untitled

N이 15라서 고르고 안고르고로 풀 수 있음

boj 15486 퇴사2

N이 150만까지 가능함 → 최적화를 해줘야함 → 개날먹 쌉가능

public class Main {
	static int n, m, k, result;
	static int[][] arr;
	static int[] dp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		arr = new int[n][2];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
		dp = new int[n + 51];
		Arrays.fill(dp, -1);
		dp[n] = 0;
		for (int i = n - 1; i >= 0; i--) {
			if (i + arr[i][0] > n) {
				dp[i] = dp[i + 1];
			} else {
				dp[i] = Math.max(dp[i + 1], dp[i + arr[i][0]] + arr[i][1]);
			}
		}

		System.out.println(dp[0]);
	}

	static int recur(int cur) {
		if (cur == n) {
			return 0;
		}
		if (dp[cur] != -1) {
			return dp[cur];
		}
		if (cur > n) {
			return -2_000_000_000;
		}
		dp[cur] = Math.max(recur(cur + arr[cur][0]) + arr[cur][1], recur(cur + 1));
		return dp[cur];
	}
}

Untitled