[PS] BOJ15486 퇴사2 ( dp ) with JAVA

15486번: 퇴사 2

 

◎ 문제풀이

 

DP 점화식 구현이 까다로운 문제였다.

 

 

 

 

7일에 받을 수 있는 상담의 경우의 수는 다음과 같다.

 

1일에 시작된 상담이 6일 걸려 7일이 될 수 있고

3일에 시작된 상담이 4일 걸려 7일이 될 수 있다

 

그리고

 

만약 전날에 마무리 된 상담비용이 더 크면 그대로 7일의 상담비용이 된다.

 

이와 같이, 7일이 될 수 있는 모든 경우의 수에서 최댓값을 구하면 된다.

 

 

◎ 코드

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

import static java.lang.Math.*;

//BOJ15486 퇴사2
public 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[] dp = new int[n+2];
        int maxCost = 0;


        StringTokenizer st;
        for(int i=1;i<=n;i++){

            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());

            //현재 날짜 DP 갱신
            //전날 비용이 더 크면 그대로 가져온다.
            dp[i] = max(dp[i],dp[i-1]);

            //다음 날짜 DP 갱신
            int next = i+t;
            if( next > n+1 ) continue;
            dp[next] = max(dp[next],dp[i]+p);
            maxCost = max(maxCost,dp[next]);

        }

        System.out.println(maxCost);

    }
}