[BOJ] 백준 14501 - 퇴사 (자바)

DP...,, DFS(?)...,,

2017년 상반기 CE/IM 2번 문제

나는 DP로 풀었다. 예전에는 못풀었는데 프로그래밍을 하다보니 실력이 늘긴 했나보다..

풀이

1. T[], P[], dp[] 배열을 사용한다.

T[] 배열은 날짜, P[] 배열은 수입금, dp[]는 당일까지 최대 수입금 을 저장한다.

2. 첫 날부터 마지막날 까지 계산하는데 계산중인 날 기준으로 이전보다 최대수입이 작으면 안된다.

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

3. (현재 날짜 + 상담 완료) 날짜의 수입금은

(현재 날짜 + 상담 완료)날짜에 저장된 최대 수입과 와 (오늘 이전까지 최대 수입 + 오늘 버는 수입) 중 최대값을 저장한다. 

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

4. 최대수입을 저장한다.

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

아 설명 진짜 못한다. 아무튼 코드를 보다보면 이해 할 수 있을 꺼에요....

소스

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
 
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
 
        int N = Integer.parseInt(br.readLine());
 
        //N+10 을 해준 이유는 마지막날 + 5일일 때 배열 에러가 날 수 있으므로 넉넉히 잡아준다. 
        int[] T = new int[N+10];
        int[] P = new int[N+10];
        int[] dp = new int[N+10];
        int max = 0;
        String[] str;
        for (int i = 1; i <=N; i++) {
            str = br.readLine().split(" ");
            T[i] = Integer.parseInt(str[0]);
            P[i] = Integer.parseInt(str[1]);
        }
        //------------입력부------------//
        
        
        for (int i = 1; i <=N+1; i++) {
            //이전까지의 최대 수입을 비교해서 최대 수입을 현재에도 저장해준다.
            //이전에 최대수입이 났을 수 있으므로
            //ex) 3,7,(5 예상) 이라고 하면 5의 값은 7로 바꿔주는게 최대수입을 얻는데 맞다.
            dp[i] = Math.max(dp[i], max);
            //이전에 저장된 최대수익 vs 이번 움직임으로 생긴 최대 수익
            dp[T[i]+i] = Math.max(dp[T[i]+i],P[i]+dp[i]);
            //출력될 최대 수입
            max = Math.max(max, dp[i]);
            
        }
        System.out.println(max);
    }
}