BOJ_14501_퇴사(C++) [DFS or Dynamic Programming]

PS 백준 소스 코드 모음 : https://github.com/kgw4073/Problem-Solving

---

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

14501번: 퇴사

마시멜로 이야기를 아는가??!! 지금 하나를 먹으면 다음 마시멜로는 없지만, 지금 30분 동안 꾹 참으면 마시멜로를 무려 두 개나 먹을 수 있다는 사실!  이 이야기는 내가 생각하기에 완전 탐색을 쉽게 이해하게 하는 예시라고 생각한다. 모든 경우의 수를 열어 놓는 것. 모든 경우의 수를 열어 놓기 위해 지금 눈 앞에 있는 이득을 꾹 참는 것. 그것이 완전 탐색, 어쩌면 Dynamic Programming의 핵심이다. 그래서 이들은 Greedy Algorithm과 비교되는 알고리즘으로 분류된다.

* PS를 어느 정도 했던 사람이라면 이 문제를 보자마자 DP로 풀면 되겠다는 감이 올 것이다. 먼저 DP로 푸는 방법을 설명하고 DFS를 이용하여 푸는 방법을 설명하겠다.

---

Dynamic Programming

프로그래밍을 할 때는 처음부터 세밀하게 설계하는 것이 아니라 우선 크게 크게 틀만 잡아두고 가는 것이 좋다.

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200

자. 위의 예시로 살펴보자. 아무 날짜나 잡아보자. 대충 현재 2일에 일할지 말지를 결정한다고 해보자.

depth = 2로 두겠다.

그러면 2일에 일할지 말지 결정하기 위해서는, 2일을 선택했을 때 이득과, 선택하지 않은 채 꾹 참고 다음 날로 넘어갔을 때의 이득을 비교해야 한다. 만약 2일을 선택했다면 5일동안 일을 못하므로

현재 날짜가 7일일 때 얻는 이득 + 2일을 선택함으로써 얻는 20원

이 된다.

만약 2일을 선택하지 않았다면 그냥 다음 날로 넘어가서

3일로 그냥 넘어갔을 때의 얻을 이득

이 된다.
즉, 현재 날짜가 2 + T[2], 즉, 7일일 때 얻는 이득 + 2일을 선택함으로써 얻는 P[2], 즉, 20원 VS 2일을 선택하지 않고 다음 날인 3일로 넘어감으로써 얻는 이득

이 두 값을 비교해야 한다.

이제 depth 가 2라고 했으므로 2를 depth로 바꿔보자.

depth + T[depth] 일 때 얻는 이득 + P[depth] VS depth+1일 때 얻는 이득

이 된다.

끝났다.

물론 1차원 DP이기 때문에 이렇게 간단한 점화식으로 나오긴 기본적인 틀은 이런 식이다.
재귀호출을 어렵게 생각하지 않아도 된다. 우리가 수학에서 배웠던 점화식과 똑같다.

이것을 코드로 나타내면 다음과 같다.

#include <iostream> #include <vector> #include <algorithm> using namespace std; int n; vector<pair<int, int>> vec; // dp table int cache[16]; const int inf = 2e9; // Dynamic Programming (1차원 DP) int solution(int depth) { // n + 1보다 크면 선택을 아예 못하니까, 이걸 선택 못하게 하도록 엄청나게 작은 수를 리턴 if (depth > n + 1) return -inf; // n + 1일이면 선택은 못하지만 지금까지 선택된 것들은 가져갈 수 있으므로 0을 리턴 if (depth == n + 1) return 0; // 뭔가 저장돼 있으면 그걸 반환 if (cache[depth]) return cache[depth]; // cache 에 지금 날짜를 선택 안한 경우 solution(depth + 1)과 // 현재 날짜를 선택하고 다음 걸로 넘어간 경우와 비교한 것 중 큰 것을 저장 return cache[depth] = max(solution(depth + 1), solution(depth + vec[depth].first) + vec[depth].second); } int main() { cin >> n; // 디버그시 편의상 인덱스 0번에 (0, 0)을 저장 vec.emplace_back(0, 0); for (int i = 1; i <= n; i++) { int time, price; cin >> time >> price; vec.emplace_back(time, price); } cout << solution(1); }

---

DFS (Brute force)

DFS도 사실 DP의 논리 구조와 다를 바 없다. 그냥 DFS 하는 도중에 DP Table에 저장하는 것 빼고는 다를 게 없다. 원래 DP는 완전 탐색의 중복 탐색을 방지하기 위해 중간 중간 결과를 저장하는 것만 더해 준 것이기 때문이다.

즉, 현재 날짜가 2 + T[2], 즉, 7일일 때 얻는 이득 + 2일을 선택함으로써 얻는 P[2], 즉, 20원 VS 2일이 선택하지 않고 다음 날로 넘어감으로써 얻을 이득

이걸 완전히 그대로 사용하면 된다.
depth + T[depth] 일 때 얻는 이득 + P[depth] VS depth+1일 때 얻는 이득

다만 depth + T[depth] 가 n+1보다 작거나 같을 때 탐색하는 것으로 해두는 정도이다.

#include <iostream> #include <vector> #include <algorithm> using namespace std; int n; vector<pair<int, int>> vec; int mx = 0; void solution(int depth, int price) { // depth가 n + 1일 까지 왔다면 if (depth == n + 1) { mx = max(mx, price); return; } // 현재 depth 선택 안하고(꾹 참고) 다음 날짜 탐색 solution(depth + 1, price); // n + 1일에서 벗어나는 것은 탐색할 필요가 없음 if (depth + vec[depth].first <= n + 1) { solution(depth + vec[depth].first, price + vec[depth].second); } } int main() { cin >> n; vec.emplace_back(0, 0); for (int i = 1; i <= n; i++) { int time, price; cin >> time >> price; vec.emplace_back(time, price); } solution(1, 0); cout << mx; }

---

재귀 호출을 어렵게 생각하지 말자. 수열의 점화식만 있으면 우리는 아무리 큰 번호의 수열이더라도 값을 구할 수 있지 않은가? 마찬가지이다. 점화식만 세우자. 그리고 지금 함수의 인자가 말 그대로 '그냥' 어느 값이 주어졌다고 해보자. 그렇게 외생적으로 주어진 인자들에 대해 케이스를 나누고, 점화식을 재귀 함수로 그대로 옮기면 된다. 나머지는 과정들은 알아서 점화식이, 즉, 재귀 함수가 해 줄 것이다.

이토록 재귀 함수 노래를 부르는 이유는 나도 재귀 함수가 정말 어려웠기 때문이다. 그런데 어느 순간, 어차피 나머지 일은 재귀 함수가 알아서 처리해 준다는 사실을 깨닫고 나서 웬만한 완전 탐색 문제들은 금방 해결하기 시작했다. 그러니까 겁먹지 말고 재귀 함수에 도전해보자. 아, 물론 반복문으로 짤 수 있는 것을 일부러 재귀 함수로 짜는 것은 추천하지 않는다. 재귀 함수는 계속해서 시스템 스택에 쌓아나가기 때문에 depth가 조금만 커져도 프로세스에 큰 무리가 가기 때문이다. 우리가 자주 사용하는 Microsoft Visual C++에서는 depth가 5000 정도 넘어가면 되어도 stack overflow가 발생한다.

사설이 길었지만, 요약하자면 이 문제와 같이 아주 간단한 DFS를 이용한 완전 탐색이나 Dynamic Programming 문제들로 점화식을 세우는 습관을 세워보자. 그러한 연습이 앞으로 여러분들이 맞닥뜨리게 될 코딩 테스트에서 큰 힘이 될 것이다.