[백준] 14501번 - 퇴사, 15486번 - 퇴사 2 (C++)

문제

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

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

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

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

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

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	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)

 

퇴사2

첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다.

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

---

출력

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

---

예제 입력 1 복사

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

예제 출력 1 복사

45

예제 입력 2 복사

10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

예제 출력 2 복사

55

예제 입력 3 복사

10
5 10
5 9
5 8
5 7
5 6
5 10
5 9
5 8
5 7
5 6

예제 출력 3 복사

20

예제 입력 4 복사

10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50

예제 출력 4 복사

90

---

풀이과정

해당 문제는 dp알고리즘으로 분류되어있는 문제로 새로운 알고리즘 개념을 대입을 해서 풀어야 했던 문제였다.

다이나믹 프로그래밍이란 "특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘"

이라고 명시가 되어있는 알고리즘이다.

즉 위와 같은 퇴사문제의 값을 구할 때 모든 경우의 수를 다 돌려보는 것이 아니라 이전에 구해두었던 다른 값을 참조해서 현재의 값을 구하는 시간단축을 할 수 있는 알고리즘 방법이라고 생각하면 된다.

 

	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	X	0	0	0

위에 문제에 dp를 대입하여 설명을 해보자면 문제에서는 최종적으로 얻을 수 있는 최대수익이 몇인가를 중요한 포인트로 생각하면 된다.

최대수익은 결과적으로 가장 마지막 부분중에 해당이 되겠지만 dp라는 것 자체가 최대수익이라는 값을 구하기 위해서 다른 범위의 값까지 이용하여 활용하는 방식을 이야기하기 때문에 최대수익이 되기까지의 전 과정들이 어떻게 이루어져 있는가를 중점적으로 봐서 값을 구하는 방식을 이야기한다.

위에 표에서 최대수익이 되는 기준이 10+20+15=45에 해당이 되는 값이기때문에 이전에 벌어들은 수익은 계속 더해가며 계산이 되는 형식이라는 것을 볼 수 있고, 위에 있는 표를 기준으로 최종적인 최대수익만 생각하는 것이 아니라 X라는 날이 있으면 그날에 얻을 수 있는 최대 수익은 몇인가라고 바꿔 생각을 하여 이전에 있는 값들을 인용해서 후에 값을 계산하는 방식으로 생각하면 된다.

(dp에는 그날 벌어드릴 수 있는 최대 수익이 적힌다.)

	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	0	0	0

 

1일차의 경우에는 기간이 3일이기 때문에 10에 해당하는 보수는 4일 차에 들어오는 형식이라고 생각을 할 수 있다. 이러한 형식으로 모든 값들을 dp에 다 담다 보면 

	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	0	0	20

3일 차에는 기간이 1이라서 4일에 바로 수익이 들어오는 형식인데 4일 차에 이미 해당하는 위치에 값이 적혀있어서 값을 적을 수 없는 상황이 나오게 된다.

그런 경우에는 1일차와 3일 차가 서로 다른 경로로 4일 차에 도달을 한 경우라서 4일 차의 입장에서 보면 둘 중 어떠한 값이 적혀도 이전 결과에 따라서 이미 도달되어 온 값들이기 때문에 4일 차가 나아가는 데에 있어서는 전혀 상관이 없다는 것을 알 수 있다.

그래서 해당 문제에서는 최대 수익을 구하는 형식으로 문제가 주어졌기 때문에 4일차에 이미 적혀있는 dp에 값과 새롭게 들어올 값을 비교해서 더 큰 값을 적으면 되는 방식이다. DP [4일 차] = max(DP [4일 차], N(새롭게 들어올 값))

위에 경우에는 1일차의 값도 10이고 3일 차의 값도 10이므로 크게 상관하지 않고 진행하게 된다.

	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	20

위와 같이 4일 차의 해당하는 값을 5일 차(기간이 1이므로)에 적어야 하는 경우에는 계산하는 날에 dp에 이미 적혀있는 값을 그대로 가지고

5일 차에 적으면 된다. (4일 차 : 20 + dp : 10 = 30 )

	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

이러한 형식으로 계속 계산을 하다 보면 우리가 구하자고 했던 최대수익의 값을 찾을 수 있는 것을 알 수 있다.

이러한 형식으로 전개가 된다고 생각을 하면 된다.

 

추가적인 반례로는 위에 표상으로는 6일 차에 dp(최대수익)이 0으로 적혀있지만 5일차에 수익이 30이므로

6일차에 일을 아예 안 한다고 해도 6일 차의 수익은 이전에 최대 수익값을 가져야 한다.

그래서 진행을 해가면서 dp의 값이 비워져 있다면 채워 넣어주는 식도 추가적으로 넣어줘야 한다.

---

14501번 - 퇴사

15486번 - 퇴사 2

14501문제가 15486문제와 형식만 똑같고 주어지는 크기만 다르기 때문에 퇴사문제의 코드를 dp형식으로 구성을 해두었다면 퇴사2 문제도 배열값만 바꿔서 그대로 풀 수 있었다.

 

code

// 14501번 - 퇴사
#include <iostream>
#include <algorithm>

int		main(void)
{
	int n, max = -1;
	int tp[16][2] = {0,}, dp[16] = {0,};

	std::cin >> n;
	for (int i = 0; i < n; i++)
		std::cin >> tp[i][0] >> tp[i][1];

	for (int i = 0; i <= n; i++) {
		int deadline = i + tp[i][0];
		if (max > dp[i]) dp[i] = max;
		if (deadline <= n)
			dp[deadline] = std::max(dp[deadline], tp[i][1] + dp[i]);
		if (dp[i] > max) max = dp[i];
	}
	std::cout << max;

	return (0);
}

// 15486번 - 퇴사 2
#include <iostream>
#include <algorithm>

int		main(void)
{
	int n, max = -1;
	int tp[1600000][2] = {0,}, dp[1600000] = {0,};

	std::cin >> n;
	for (int i = 0; i < n; i++)
		std::cin >> tp[i][0] >> tp[i][1];

	for (int i = 0; i <= n; i++) {
		int deadline = i + tp[i][0];
		if (max > dp[i]) dp[i] = max;
		if (deadline <= n)
			dp[deadline] = std::max(dp[deadline], tp[i][1] + dp[i]);
		if (dp[i] > max) max = dp[i];
	}
	std::cout << max;

	return (0);
}

 

---

후기

dp라는 개념을 이번에 새롭게 다잡자라는 느낌으로 알고리즘에 대해서 공부를 해봤었는데 확실히 어렵다는 느낌을 많이 받았다.

코테를 보거나 기본적으로 가장 많이 쓰이는 알고리즘 중에 하나이기 때문에 익숙해질 때까지 dp를 계속 풀어봐야 할 거 같다.