[C++] 백준 14501 퇴사

문제 링크

---

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

14501번: 퇴사

 

접근 방법

---

동적계획법을 사용하여 풀이하였으며, 재귀함수를 이용한 top-down방식을 사용하였으며 크게 어렵지 않은 문제였다.

 

(1) 변수

   dp[i]는 i번째 날부터 상담을 하기 시작하였을 때 가질 수 있는 최대의 비용이다.

 

(2) solve( )

   함수 내에서 cur은 현재 날짜를 의미한다.

if (cur > n + 1) 
	return -1;
if (cur == n + 1) 
	return dp[cur] = v[cur].second; //딱 마지막 날이면 그값을 반환

 첫번째 if문은 현재날짜가 퇴사일을 지나간 경우이고, 두번째 if문은 정확히 퇴사 날짜를 포함하여 현재 상담이 종료되는 경우이다. 이 두가지 조건이 아니라면 다음 상담을 잡을 수 있는 가능성이 존재한다는 것이다. 

for (int i = cur + v[cur].first; i <= n + 1; i++) { //미팅이 시작 가능한 경우의 한에서
	int ret = solve(i);
	if (ret != -1) 
		dp[cur] = max(ret + v[cur].second, dp[cur]);
}
return dp[cur];

 

 i는 현재 날짜로 부터 상담을 마친 이후 가능한 모든 다음 상담의 시작 날짜이다. 하지만 위 for문에서 (i > n+1), 즉 상담날짜의 시작시점이 퇴사일이 지난 이후라면 자연스럽게 무시가 될것이다.  max( )에서 ret + v[cur].second는 현재의 상담에 대한 비용을 계속해서 더해나간 것이고, 메모되었던 dp[cur]와 비교를 하여 더 큰 값으로 갱신 할 것이다. 

 

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<pair <int, int>> v(20, {0,0});
int dp[17];
int n;

int solve(int cur) { //1
	if (cur > n + 1) 
		return -1;
	if (cur == n + 1) 
		return dp[cur] = v[cur].second; //딱 마지막 날이면 그값을 반환
	
	else { //만약 next로 진입이 가능하다면 
		for (int i = cur + v[cur].first; i <= n + 1; i++) { //미팅이 시작 가능한 경우의 한에서
			int ret = solve(i);
			if (ret != -1) 
				dp[cur] = max(ret + v[cur].second, dp[cur]);
		}
		return dp[cur];
	}
}

int main() {
	cin >> n;
	v[0] = {1,0};
	for (int i = 1; i <= n; i++) {
		int t, p;
		cin >> t >> p;
		v[i] = { t,p };
	}
	cout << solve(0) << endl;
}

개발 환경 : VS 2019

질문, 지적 환영입니다.