[자바] 백준 14501번: 퇴사

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

14501번: 퇴사

 

퇴사하기 전까지 얼마나 벌 수 있는지 계산하는 문제.

 

다이나믹 프로그래밍 dp로 풀 수 있다.

 

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

public class P14501 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int[] T = new int [n+1];
		int[] P= new int[n+1];
		for(int i=1;i<=n;i++) {
			st= new StringTokenizer(br.readLine());
			T[i] = Integer.parseInt(st.nextToken());
			P[i]=Integer.parseInt(st.nextToken());
		}
		
		int[] dp = new int [n+2];
		
		for(int i=1;i<=n;i++) {
			if(dp[i]<dp[i-1])//최댓값으로 갱신
				dp[i]=dp[i-1];
			
			if(i+T[i]>n+1)//퇴사하기전에 상담을 못 끝내는 경우
				continue;

			if(dp[i+T[i]]<dp[i]+P[i])
				dp[i+T[i]]=dp[i]+P[i];


		}
		if(dp[n+1]<dp[n])
			dp[n+1]=dp[n];
		
		System.out.println(dp[n+1]);
	}

}

dp[i]의 값은, i날에 가질 수 있는 돈의 최댓값이 저장된다고 생각하면 된다.

 

오늘 30원이 있고(dp[i]==30)

오늘부터 3일간 상담(T[i]==3)을 완료하면 30원(P[i]==30)을 받는다고 하면,

dp[i+T[i]]=max(dp[i]+P[i], dp[i+T[i]])를 하면 된다.

이 방법을 반복문을 통해 매 날마다 계산해주면 된다.

 

반복문의 맨 첫줄에는

dp[i]=max(dp[i],dp[i-1])이 있기 때문에

dp는 뒤로갈수록 점점 값이 증가하는 형태가 된다.

(참고: 반복문에서 dp의 i-1인덱스를 사용하기 위해 0번째 인덱스는 사용하지 않고 0을 담아놓았고 반복은 i=1부터 시작하도록 했다. 배열T,P의 인덱스도 편하게 사용하기 위해 배열T,P도 각각 0번째 인덱스는 사용하지 않고 0을 담아놓았다.)

 

반복을 모두 마친 후에는,

dp[1]~dp[n]까지는 반복문을 통해 점점 증가하는 값으로 저장되어있는데,

dp[n+1]의 값은 반복문을 거치지 않아 최댓값으로 갱신되지 않았을 수 있으니,

dp[n]과 dp[n+1]의 값을 비교해서 더 큰 값을 출력하면 된다.