[백준] 14501번 퇴사 자바

문제

 

14501번: 퇴사

 

 

문제 풀이

 

dp문제인건 바로 알았는데 dp를 너무 못해서 구글링하고서도 이해하는데 꽤 많은 시간이 걸렸다..

우선 dp의 크기를 N+2 로 두었다. 왜냐하면 마지막 날(N일)까지 일한건 퇴사일(N+1일)에 돈을 받을 수 있으니까 N+1일까지 누적 수익값을 구하기 위해서다.

 

dp[i]는 i일까지의 최대 이익을 저장해둔 것이다. 

1일부터 N일까지 반복하면서 해당 날짜로부터 상담을 시작해 상담이 끝난 다음 날의 dp에 해당 수익을 저장한다.

이때 해당 dp에 이미 들어있는 값과 현재 dp[i]의 값 + 현재 날짜에 상담을 함으로써 얻을 수 있는 이익과 비교한다.

 

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

 

그리고 이때 현재 dp[i]값도 그 전까지의 최대값으로 계속 갱신해주어야 해당dp[i]를 더해서 그 끝나는 상담날짜의 dp값을 갱신할 수 있다. 아래처럼 dp를 직접 그리다보면 i = 8에서 그 이유를 알 수 있음.

 

	1	2	3	4	5	6	7	8	9	10	11
T	5	4	3	2	1	1	2	3	4	5	-
P	50	40	30	20	10	10	20	30	40	50	-
dp	0	0	0	0	0	50	60	60	80	80	90

 

소스 코드

 

public class b_14501 {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] T = new int[N+1];		//걸린 날짜
		int[] P = new int[N+1];		//얻는 이익
		int[] dp = new int[N+2];	//N일 까지는 일이 가능해서 N+1일날 돈을 받을 수 있음
		
		for(int i = 1; i <= N; i++) {
			T[i] = sc.nextInt();
			P[i] = sc.nextInt();
		}
		sc.close();
		
		int max = 0;
		for(int i = 1; i <= N; i++) {
			dp[i] = Math.max(dp[i], dp[i-1]);
			
			if(i + T[i] <= N+1) 
				dp[T[i] + i] = Math.max(dp[T[i] + i], dp[i] + P[i]);//Max(기존값, 현재최대수익+i번째 일 수행)
			
			max = Math.max(max, dp[i]);
		}
		
		max = Math.max(max, dp[N+1]);
		System.out.println(max);
	}

}