[백준 14501] 퇴사 (자바)

백준 14501번 퇴사 (자바)

 

 

 

출처

www.acmicpc.net/problem/14501

14501번: 퇴사

 

 

 

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

3	5	1	1	2	4	2
10	20	10	20	15	40	200

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

 

 

 

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

 

 

 

출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

 

 

 

입출력 예

입출력 예 1

입출력 예 2

 

 

 

접근 방법

기존 퇴사문제는 조건 범위가 작아 완전 탐색으로 풀 수 있지만, 이 문제는 범위가 커서 DP로 풀어야 한다.

기존 퇴사문제에서 사용했던 방식으로 점화식은 쉽게 세울 수 있었다.

하지만, 계속 맞왜틀에 빠져 한참을 고민하다 다른 분의 코드를 참고하였다.

 

현재 i에서 상담일(t[i])를 더해 범위를 초과하지 않는 경우 dp 배열에 금액(p[i])를 더해준다.

점화식 : if (i + t[i] <= n) dp[i] = max(dp[i + t[i]], dp[i + t[i]] + p[i])

 

위 점화식대로 연산을 진행하면 주어진 첫 번째 예시에서 최대 금액은 45이다.

ex) 1 (+3, 10) -> 4 (+1, 20) -> 5 (+2, 15) = 7 (+2, 45) (7+2는 7을 넘어서기 때문에 연산 불가능)

 

이를 그림으로 나타내면 아래와 같다.

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200
dp	0	0	0	10	30	0	45

 

여기서 이상한 점을 찾을 수 있다.

 

2, 3, 6일에는 금액이 모두 0인 것을 확인할 수 있다.

상담은 중간에 그만두는 것이 아니라 지속되기 때문에 금액도 유지되어야 한다.

 

2,3일인 경우에는 1일의 상담금액인 10이, 6일은 경우에는 5일의 상담금액은 30이 들어가 있어야 한다.

 

이를 위해 dp[i+1] = max(dp[i+1], dp[i]) 코드를 더해주었다.

 

 

내 코드

package dynamicprogramming;

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

public class Resign2 {
	/**
	 * 백준 15486 퇴사2 (https://www.acmicpc.net/problem/15486)
	 */
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(reader.readLine());
		
		int[] t = new int[n];
		int[] p = new int[n];
		
		StringTokenizer st;
		for (int i=0; i<n; i++) {
			st = new StringTokenizer(reader.readLine());
			
			t[i] = Integer.parseInt(st.nextToken());
			p[i] = Integer.parseInt(st.nextToken());
		}
		
		//dp : N일에 얻을 수 있는 최대 수익
		int[] dp = new int[n+1];
		
		//점화식
		//현재 날짜에서 소요 시간과 비용을 더해 dp에 저장한다.
		//이후, 중복될 때 최대값을 넣는다.
		//dp[i + t[i]] = max(dp[i + t[i]], dp[i] + p[i]);
		
		for (int i=0; i<n; i++) {
			if (i + t[i] <= n) {
				//날짜가 범위를 넘어가지 않는 경우
				dp[i + t[i]] = Math.max(dp[i + t[i]], dp[i] + p[i]);
			}
			//현재 경우의 수가 0일 수 있기 때문에 이전의 최대값을 넣어줌.
			//해당 날짜에 일할 수 없다면, 이전까지 일한 최대 수당을 넣어주어야 한다.
			dp[i+1] = Math.max(dp[i+1], dp[i]);
		}
		System.out.println(dp[n]);
		
	}//main
}//Resign2

 

 

 

고려할 점

1. 상담 소요 시간을 조건에 맞게 사용할 것

2. 금액이 비는 요일을 고려할 것