[BaekJoon] 백준 14501 퇴사 - Java

 

백준 퇴사문제

 

DFS로도 풀 수 있을거 같은데 DP 연습겸 DP로 풀었다. 

 

1일부터 계산하려니 어려워서 삽질을 많이했다.

 

 

 

1일 부터 시작하기보다는 N일부터 -1 씩 거꾸로 내려오는게 쉽다.

 

문제로 예시를 들면

 

7일과 6일에는 퇴사일을 넘어가기 때문에 최대 이익이 0이다.

 

5일부터 이익을 챙길 수 있는데

 

5일부터 7일까지 일했을 때의 이익은 15이다. 

 

예제에는 3, 4일 모두 1이기 때문에 이익을 모두 가져갈 수 있지만

 

2일째에는 2일에 일하는게 더 좋은지 아니면 2일을 포기하고 기존 3일부터 7일까지 일하는게 이익인지 생각해 봐야 한다. 

 

최대값을 평가하는 법은

 

2일에 일했을때 => 현재 날짜(i)+상담에 걸리는 일(ti) = d[ i + ti ]+p[i]가 된다. 

 

위 예시에서 2일 선택 기준은

 

앞에서 계산한 6일부터 7일까지 일했을 때의 값과 2일에 상담을 했을 때의 값어치를 더하면 된다. 

 

import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();
		int[] t= new int[n+2];			//cost
		int[] p = new int[n+2];			//value
		
	
		int[] d = new int[n+2];
		
		for(int i = 1; i<=n; i++) {	
			t[i] = scan.nextInt();
			p[i] = scan.nextInt();
		}
		
	
		for(int i = n; i > 0; i--) {
			
			int cost = i+t[i];
			
			if(cost > n+1) {
				d[i] = d[i+1];
			}
			else {
				d[i] = Math.max(d[i+1], d[cost]+p[i]);
			}
			
			
		}
		System.out.println(d[1]);
		
	}
}

 

계산하기 편하게 index 1부터 시작하기로 하고, 상담에 걸리는 날이 1일 때에는 당일에 바로 끝낼 수 있기 때문에 쉽게  N+1일 까지 일을 할 수 있다고 생각할 수 있다. 

 

d[i+1] => 현재날 (i 번째)의 상담을 선택하지 않았을 때

cost = 현재 날짜 + 상담에 걸리는 날

 

d[cost] +p[i] => 현재 상담을 진행할 때의 이익

 

중에서 max값을 구하면 된다.