백준 14501번 자바 : 퇴사

백트래킹

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main { 

    static int N,ans;
    static int[] T = new int[15];
    static int[] P = new int[15];
    static int[] dp = new int[16];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }    
        dfs(0,0);  
        System.out.println(ans);
    }

    static void dfs(int cur, int sum) {
        if(cur==N) {
            ans = Math.max(ans,sum);
            return;
        }
        if(cur+T[cur]<=N) {
            dfs(cur+T[cur], sum + P[cur]);
        }
        dfs(cur+1, sum);
    }

}

DP

뒤에서부터 최댓값 dp 구하기

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main { 

    static int N,ans;
    static int[] T = new int[15];
    static int[] P = new int[15];
    static int[] dp = new int[16];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }    
        
        for(int i=N-1; i>=0; i--) {
            // dp[i]
            if(i+T[i]<=N) {
                dp[i] = Math.max(dp[i+1], dp[i+T[i]] + P[i]);
            } else {
                dp[i] = dp[i+1];
            }
        }

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

}