[백준] 14501번: 퇴사

문제링크 : https://www.acmicpc.net/problem/14501

 

문제풀이

동적계획법으로 풀 수 있는 문제이다.

1일까지 상담했을 때 최대 금액, 2일까지 상담했을 때 최대 금액을 차례로 더하여 저장해놓는다.

 

1) 1일까지 상담했을 때 최대 금액은 10이다.

 

2) (2일을 포함하여) 2일까지 상담했을 때 최대 금액은 20이다.

   왜냐하면 1일에 상담을 받으면 3일이 걸려 2일에는 상담을 받을 수 없기 때문이다.

 

3) (3일을 포함하여) 3일까지 상담했을 때 최대 금액은 10이다.

   왜냐하면 1일에 상담을 받으면 3일이 걸려 3일에는 상담을 받을 수 없고,

   마찬가지로 2일에도 상담을 받으면 5일이 걸려 3일에 상담을 받을 수 없다.

 

4) (4일을 포함하여) 4일까지 상담했을 때 최대 금액은 30이다.

 

5) (5일을 포함하여) 5일까지 상담했을 때 최대 금액은 45이다.

 

6) (6일을  포함하여) 6일까지 상담했을 때 최대 금액은 70이다.

   하지만 6일에 상담을 하게 되면 4일이 걸려 퇴사일까지 끝내지 못하므로 제외한다.

   7일도 마찬가지.

 

7) 결국 1일, 4일, 5일 상담을 받는 경우가 최대가 된다.

 

---

 

1일까지 상담 + 5일 상담

4일까지 상담(1일, 4일 상담) + 5일 상담

이 경우, 4일까지 상담을 받는 다는 말이 곧 1일, 4일에 상담을 받는다는 뜻이라 1일이 포함되어 있다.

그래서 1일 + 5일 상담하는 경우는 굳이 안더해도 될 것 같은데 어떻게 제외해야 할지 모르겠다.

따로 체크를 해놓자니 더 복잡해 질 것 같고.. 좀 더 생각해봐야 겠다.

 

소스코드

package baekjoon;

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

public class P14501 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] schedule = new int[2][N];
		
		int max = 0;
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int T = Integer.parseInt(st.nextToken());
			int P = Integer.parseInt(st.nextToken());

			schedule[0][i] = T;
			schedule[1][i] = P;

			int sum = 0;
			// 현재 지점까지 최대 이익
			for (int j = 0; j < i; j++) {
				if (j + schedule[0][j] <= i) {
					sum = sum < schedule[1][j] ? schedule[1][j] : sum;
				}
			}
			schedule[1][i] = P + sum;

			// 최대 이익
			if (i + T <= N) {
				max = max < schedule[1][i] ? schedule[1][i] : max;
			}
		}
		
		System.out.println(max);
		
		br.close();
	}
}