[백준] 퇴사 - 14501

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

 

해당 문제는 처음엔 백트래킹으로 풀려고 했지만 다시 확인해보니 최고 수익을 찾아야 하는 문제이기 때문에 DP로 진행하였다.

 

 

중요한 점은 범위를 넘지 않는 선에서 금액을 더해가야한다. 

if (i + workingTime[i] <= N) {
    dp[i + workingTime[i]] = Math.max(dp[i + workingTime[i]], dp[i] + prices[i]);
}

예를 들어 i=0 일때, 0+workingTime[0]=7을 넘어가지 않기 때문에 이 코드가 실행되어 dp[3]=10이 된다. 

그런데 이 코드만 계속 실행 되면 dp의 값이

0 0 0 10 0 0 0 0 
0 0 0 10 0 0 20 0 
0 0 0 10 0 0 20 0 
0 0 0 10 30 0 20 0 
0 0 0 10 30 0 45 0 
0 0 0 10 30 0 45 0 
0 0 0 10 30 0 45 0 

이렇게 변하고,누적이 되지 않는 문제가 있었다.

 

dp[i+1]=Math.max(dp[i+1],dp[i]);

위의 코드를 추가하는 것으로 매번 dp 의 값이 아래처럼 변하게 수정하였다.

0 0 0 10 0 0 0 0 
0 0 0 10 0 0 20 0 
0 0 0 10 0 0 20 0 
0 0 0 10 30 0 20 0 
0 0 0 10 30 30 45 0 
0 0 0 10 30 30 45 0 
0 0 0 10 30 30 45 45

코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] workingTime = new int[N];
        int[] prices = new int[N];

        for (int n = 0; n < N; n++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            workingTime[n] = Integer.parseInt(st.nextToken());
            prices[n] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[N + 1];

        for (int i = 0; i < N; i++) {
            if (i + workingTime[i] <= N) {
                dp[i + workingTime[i]] = Math.max(dp[i + workingTime[i]], dp[i] + prices[i]);
            }
            dp[i + 1] = Math.max(dp[i + 1], dp[i]);
        }

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