[Java] 백준 14501 퇴사

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

14501번: 퇴사

문제 설명

• N일 동안 상담을 완료해서 받을 수 있는 최대 수익 구하기.
• Ti = 상담하는데 걸리는 기간
• Pi = 상담했을 때 받을 수 있는 금액
• 상담 중인 기간에는 다른 상담을 할 수 없다.

마지막 날부터 첫째 날까지 뒤에서 앞으로 거꾸로 생각하면 더 쉽게 풀 수 있는 문제 같다.

dp [i] = i일부터 퇴사 날까지 얻을 수 있는 최대 이익이라고 하자.

 

상담일로부터 상담을 완료받기까지 걸리는 시간을 계산해 조건 (i + T [i] < N+1)을 만족시키는지 검사한다.

N+1인 이유는 상담이 걸리는 시간이 상담을 시작한 날을 포함하기 때문이다. 예를 들어, 예제 4에서 i=8일 때 T [8]=3이다. i+T [i](3+8)=11인데 사실은 10일에 끝나기 때문에 i + T [i] < N+1을 검사해주는 것이다.

1. 만약 i + T [i] > N+1이라면, 상담일이 퇴사일을 초과하는 것이기 때문에

dp [i]=dp [i+1]

2. 아니면 다음 날의 최대 이익과 당일에 상담했을 시 최대 이익을 비교하여 큰 값인

dp [i] = max(dp [i+1], dp [i+t [i]] + p [i])

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s= new Scanner(System.in);
		int N = s.nextInt();
		int time[] = new int[N+1];
		int pay[] = new int[N+1];
		int dp[] = new int[N+2];
	
		for(int i=1;i<=N;i++) {
			time[i]=s.nextInt();
			pay[i]=s.nextInt();
		}
		
		for(int i=N;i>0;i--) {
			int index=i+time[i];
			
			if(index >N+1) 
				dp[i]=dp[i+1];
			else
				dp[i]=Math.max(dp[i+1],pay[i]+dp[index]);
			
		}
		
			System.out.println(dp[1]);
		
	}
}

 

주의할 점!

만약 런타임 에러가 난다면 배열 크기를 확인해볼 것!

 -> N의 크기를 받아올 때 반복문이 N부터~1까지 수행되기 때문에 dp [N+1]~dp [1]까지의 크기를 갖는 배열이 필요하므로 배열 크기는 N+2로 설정해야 한다.

 

 

처음 코드 구현을 했을 시 첫째 날부터 마지막 날까지 생각하여 점화식을 생각했는데 dp [] 배열을 활용하기 어려웠다.

뒤에서부터 거꾸로 생각할 수 있는 연습도 많이 해야겠다..