[백준 알고리즘 풀이][C++] 14501: 퇴사

기본 개념

https://www.acmicpc.net/problem/14501
이번 문제는 제목이 너무 아름다운 두글자라 눈길이 간다. 그리고 지금 진행중인 삼성 SW 역량 기출 문제중 현재까지 유일한 DP 문제여서 또한번 눈길이 간다.

DP는 알아두면 매우 좋은 훌륭한 알고리즘 풀이 방식이지만 비교적 난이도가 높아서 출제율이 높지는 않다. 적절하게 사용한다면 최고의 알고리즘이지만 그만큼 적절한 사용처를 찾기가 쉽지도 않다.

본 문제는 상담원이 퇴사하기 전까지 얼마나 많은, 효율적인 상담을 해야 최대한 뽕을 뽑고 퇴사할 수 있는지를 계산하는 문제이다. 상담 하나당 걸리는 기간 T가 주어지고 그 상담에 따른 보수 P 또한 주어진다.

DP

우선, DP를 사용하기 위하여 메모이제이션을 사용하기 위한 변수를 새로 만들거나 기존 배열을 활용해야 할 것이다.

여기서는 이미 주어진 P 배열이 우리가 사용하기에 매우 적절한 배열인데, 어차피 우리는 보수의 최댓값을 구하는 중이기 때문이다.

점화식

이제 주어진 상황에서 점화식을 한번 생각해보도록 하자.

만약 (i + T[i] > n) 라면
P[i] = P[i+1] 

아니라면
P[i] = max(P[i+1], P[i] + P[i + T[i]])

이런식이 될 것이다. 여기서 우선 중요한 포인트는 두가지인데, 첫번째는 i + T[i] < n 이부분이다. i + T[i]라는 말은 현재의 일, 즉 i번째 일에 받은 일이 끝나는 시간을 의미한다. 이 값이 n보다 크다는 의미는 이 일은 퇴사 전에 끝마칠 수 없는 일이라는 의미가 된다. 따라서 i번째 일에 받은 일은 수임할 수 없기 때문에 P[i] = P[i+1], 즉 다음날의 값과 동일하게 설정해두면 된다.

만약 i번째 일이 수임 가능하다면, 이제 i번째 일을 수임할지 말지를 생각해보아야 한다.

P[i] = P[i+1]라는 의미는 위에서 말한대로 다음날의 값을 가져오는 것이다. 다른말로 하면 오늘의 일을 수임하지 않는다는 의미가 된다. P[i] = P[i] + P[i + T[i]]라는 의미는, 오늘의 일을 수락한다는 의미이다. 오늘 할 일의 비용(P[i])과 오늘 일을 처리하고 난 다음날의 최대치(P[i + T[i]])를 더해주면 오늘부터 마지막날까지의 최대 수익이 나오게 될 것이다.

코드

여기서 주의할 점은 우리는 마지막날부터 첫째날까지 iteration을 돌리게 되는데, 그 이유는 본 문제는 근본적으로 특정 날짜부터 마지막날까지 일했을 때의 최대값을 구하는 문제이기 때문이다.

물론 반대로 첫째날부터 마지막날까지 구하도록 recursion 함수로 만들어서 푸는 방법도 있으나, 어차피 위의 재귀식대로라면 결과값은 뒤에서부터 계산되서 앞으로 더해지게 되기 때문에 stack 낭비가 되고 시간도 늘어날 것이다.

for(int i = n - 1 ; i >= 0 ; i--) {
	if(i + t[i] > n) {
		p[i] = p[i+1];
	} else {
		p[i] = max(p[i+1], p[i] + p[i + t[i]]);
	}
}

위의 점화식에 맞추어 계산하면 위와 같은 코드가 작성되게 되는데, 단순하게 배열 맨 뒤에서부터 첫번째날까지 쭉 훑어 내려오는 모습을 볼 수 있다. 이 식을 가지고 문제에서 주어진 예제를 살펴보도록 하자.

위의 입력이 문제에서 주어신 식인데, 맨 마지막인 7일부터 차례로 계산해보자.

i + T[i] > n

i + T[i] > n

P[i] + P[i + T[i]] > P[i+1]

P[i] + P[i + T[i]] > P[i+1]

P[i] + P[i + T[i]] > P[i+1]

P[i] + P[i + T[i]] < P[i+1]

P[i] + P[i + T[i]] == P[i+1]

따라서 결과값은 45가 된다. 여기서 P[i] + P[i + T[i]] > P[i+1]인 경우, 즉 3일, 4일, 5일의 수익인 10 + 20 + 15 = 45가 나온 것으로 보면 문제가 원하는 대로 완벽하게 짜여졌다는 것을 알 수 있다.

이제 입력 부분과 함께 완전한 코드를 작성하면 아래와 같다.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	
	int n;
	int t[16] = {0, };
	int p[16] = {0, };
		
	cin >> n;
	for(int i = 0 ; i < n ; i++) {
		cin >> t[i] >> p[i];
	}
	for(int i = n - 1 ; i >= 0 ; i--) {
		if(i + t[i] > n) {
			p[i] = p[i+1];
		} else {
			p[i] = max(p[i+1], p[i] + p[i + t[i]]);
		}
		
	}
	
	cout << p[0] << endl;
	
}

몇가지 주의해야할 점이 있는데, T와 P의 배열 길이를 15가 아닌 16으로 두어야 한다는 점이다. 본 문제의 n값은 원래 최대 15라고 주어지지만, 우리는 문제에서 마지막날의 경우 P[i] = P[i+1]을 해주도록 되어있기 때문에 P[14] = P[15]를 해주기 위하여 배열 길이를 최대보다 1 더해주어야 한다.

마무리

본 문제는 태그에 DP와 더불어 Brute-Force 태그 또한 달려있다. 브루트포스 방식으로 푸는 것은 물론 가능하다. 아무 생각 없이 만들기에는 매우 적합한 방식일 것이다. 최악의 경우만 보더라도, 15일치 일이 전부 들어오게 된다면 기하급수적인 시간복잡도를 가지게 된다는 것을 알 수 있다.

DP는 사실 나에게도 조금 어려운 개념이다. 아니, 개념은 이해하고 있지만 머리가 그렇게 잘 돌아가지 않는다. 아무래도 이러한 방식의 개발은 실전에서 크게 사용되지 않기 때문일 것이다. 다만, 특정 상황에서만큼은 확실하게 좋은 알고리즘인 것은 틀림없기 때문에 다양한 DP 알고리즘 공부를 해보아야겠다.