[BOJ] 14501 - 퇴사

문제 링크

14501-퇴사

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.
둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

문제 풀이

dp로 푸는 문제
되게 흔한 문제라고 생각되는데
한번에 dp의 의미를 생각해내기가 어려워..

이번 문제에서는 dp를 생각할 때, 앞이 아닌 뒤에서부터 시작하는 방식을 접했다.
참고한 글은 링크로!

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n + 1];
        int[] times = new int[n];
        int[] pays = new int[n];


        for (int i = 0; i < n; i++) {
            int time = sc.nextInt();
            int pay = sc.nextInt();
            times[i] = time;
            pays[i] = pay;
        }

        for (int i = 0; i < n; i++) {
            if (i + times[i] <= n) {
                dp[i + times[i]] = Math.max(dp[i + times[i]], dp[i] + pays[i]);
            }
            dp[i + 1] = Math.max(dp[i + 1], dp[i]);
        }
        System.out.println(dp[n]);
        
        
        /**
        for (int i = n - 1; i >= 0; i--) {
            if (i + times[i] >= n) {
                dp[i] = dp[i + 1];
            } else {
                dp[i] = Math.max(dp[i + 1], pays[i] + dp[i + times[i]]);
            }
        }
        System.out.println(dp[1]);
        **/
    }
}