7. [백준 14501번 / C++] 퇴사

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

14501번: 퇴사

 

문제를 찬찬히 읽어보면, 몇 개의 조건이 있다.

 

1. 백준이는 N일 이후 상담을 해선 안된다.

2. 스케줄표의 상담 시간은 그 당일을 포함해 상담을 진행한다. 예를 들어 문제의 예시인 1일차의 상담을 실시한다면 3일의 시간이 걸리고 즉, 1, 2, 3일차를 소비하는 것이다.

3. 퇴사 전 이익을 최대로 해라.

 

결국 우리가 고려해야하는 것은 어떤 일자에 대해서 상담을 하느냐? 마느냐?를 결정하는 것이 핵심적인 것이다.

 

1. 어떤 일자에 상담을 한다면 상담에 걸리는 시간만큼 날짜가 지나고 다시 재귀적으로 상담을 할지 말지 판단한다.

2. 상담을 하지 않는다면 그냥 하루 푹쉬고 다음날로 넘어가 다시 재귀적으로 상담을 할지 말지 판단한다.

3. N + 1이 되면 종료한다.

 

이때, 조건 1에 위배되지 않도록 하는 것을 주의해야 한다.

 

이 문제의 경우 N의 범위가 1 <= N <= 15이기 때문에 여러 알고리즘으로 풀이가 가능할 것 같은데 나는 DP로 풀었다. 코드는 다음과 같다.

 

#include<bits/stdc++.h>
using namespace std;
int n, t, p, dp[21];
pair<int, int> a[16];

int go(int idx){ // dp 함수
	if(idx == n) return 0; // 탈출
	
	int &ret = dp[idx]; // 메모라이제이션
	if(ret != 0) return ret;
	
    // 조건을 고려한 최대값을 구하는 로직
	if(idx + a[idx].first <= n) ret = max(ret, go(idx + a[idx].first) + a[idx].second);
	ret = max(ret, go(idx + 1));
	
	return ret;
}
int main(){
	cin >> n;
	for(int i = 0; i < n; i++){ // 상담 입력받기
		cin >> t >> p;
		a[i] = {t, p};
	}
    
	cout << go(0) << "\n";
	return 0;
}