[BOJ][백준 15486] 퇴사 2 - C++

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

백준 사이트의 15486번 문제, 퇴사 2 문제다.

본인은 C++로 문제풀이를 진행하였다.

---

0. 문제 읽기

상담 날짜를 정해보자

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

---

1. 문제풀이 아이디어

• DFS와 같아보이지만.. N이 무려 백오십만이기 때문에 시간이 터져버린다!
• Dynamic Programming(DP)을 사용하여 최적의 해를 찾는 문제.
• Memoization을 통해 중복 계산을 피하고, 이전에 계산한 값을 재활용한다.
•  getMoney(Day) 함수를 통해 Day일부터 시작하여 얻을 수 있는 최대 수익을 반환한다.
• Day일에는 Scdl[Day][0]일 동안의 상담 중 하나를 선택할 수 있으며, 선택한 상담의 수익과 그 다음날의 getMoney()의 반환값을 더한 값을 Memo[Day]에 저장한다.
• 모든 Day에 대해 반복하며 Memo[Day]를 업데이트하여 최대 수익을 찾는다.
• 마지막으로 getMoney(1)을 호출하여 1일부터 시작하는 최대 수익을 구하고, 이를 출력한다.

---

2. 코드 핵심 부분

1) DP 알고리즘을 실행하는 함수,

   본인은 DP 알고리즘의 방식 중에

   Memorization, Top-Down 방식으로 구현하였다.

   Top-Down 방식은 재귀 호출을 사용하고 Tabulation 방식보다 시간이 약간 오래 걸리지만 구현하기 쉽다는 장점이 있다.

   Tabulation, Bottup-up 방식은 점화식에 대한 이해가 필요하다.

   재귀 호출 없이 반복문으로 구현되기 때문에 실행시간과 메모리에 이점이 있다.

// DP 실행
int getMoney(int Day) {
	if (Day > N) // Day가 N보다 크면 더 이상 상담이 불가능한 경우이므로 0을 반환
		return 0;

	if (Memo[Day]) // 이미 계산한 값이 Memo[Day]에 저장되어 있다면 그 값을 반환하여 중복 계산을 피함
		return Memo[Day];

	int Max = 0; // 최대 수익을 저장하는 변수

	for (int i = 0; i < Scdl[Day][0]; i++) { // Day일에 가능한 상담 중에서 선택
		int Now = Day + i; // 현재 상담의 종료일

		if (Now + Scdl[Now][0] > N + 1) // 현재 상담을 선택했을 때 N을 초과하면 상담이 불가능하므로 continue
			continue;

		int ret = getMoney(Now + Scdl[Now][0]) + Scdl[Now][1]; // 현재 상담을 선택하고, 그 다음날부터 시작하는 최대 수익 계산

		if (ret > Max) // 현재 선택한 상담의 수익이 이전에 계산한 최대 수익(Max)보다 크다면, Max를 업데이트
			Max = ret;
	}

	Memo[Day] = Max; // Memo[Day]에 최대 수익(Max)을 저장하여 중복 계산을 피함
	return Memo[Day];
}

---

3. 전체 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

/*
1. 문제읽기
- 상담기간과 상담 수익이 주어지는 문제.
- 하루에 하나의 상담만 가능하고, 상담을 완료한 다음날은 상담을 할 수 없다.
- 상담을 선택할 때, 상담 기간과 상담 수익을 고려하여 최대의 수익을 얻는 문제.

2. 아이디어
- Dynamic Programming(DP)을 사용하여 최적의 해를 찾는다.
- Memoization을 통해 중복 계산을 피하고, 이전에 계산한 값을 재활용한다.
- getMoney(Day) 함수를 통해 Day일부터 시작하여 얻을 수 있는 최대 수익을 반환한다.
- Day일에는 Scdl[Day][0]일 동안의 상담 중 하나를 선택할 수 있으며, 선택한 상담의 수익과 그 다음날의 getMoney()의 반환값을 더한 값을 Memo[Day]에 저장한다.
- 모든 Day에 대해 반복하며 Memo[Day]를 업데이트하여 최대 수익을 찾는다.
- 마지막으로 getMoney(1)을 호출하여 1일부터 시작하는 최대 수익을 구하고, 이를 출력한다.
*/

// 필요 인자들
int N; // 상담기간 (1 ≤ N ≤ 1,500,000)
int Scdl[1500001][2]; // 상담 스케쥴, 1일부터 저장
int Memo[1500001]; // DP 메모용

// 값 입력받는 함수
void input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> Scdl[i][0] >> Scdl[i][1];
	}
}

// DP 실행
int getMoney(int Day) {
	if (Day > N) // Day가 N보다 크면 더 이상 상담이 불가능한 경우이므로 0을 반환
		return 0;

	if (Memo[Day]) // 이미 계산한 값이 Memo[Day]에 저장되어 있다면 그 값을 반환하여 중복 계산을 피함
		return Memo[Day];

	int Max = 0; // 최대 수익을 저장하는 변수

	for (int i = 0; i < Scdl[Day][0]; i++) { // Day일에 가능한 상담 중에서 선택
		int Now = Day + i; // 현재 상담의 종료일

		if (Now + Scdl[Now][0] > N + 1) // 현재 상담을 선택했을 때 N을 초과하면 상담이 불가능하므로 continue
			continue;

		int ret = getMoney(Now + Scdl[Now][0]) + Scdl[Now][1]; // 현재 상담을 선택하고, 그 다음날부터 시작하는 최대 수익 계산

		if (ret > Max) // 현재 선택한 상담의 수익이 이전에 계산한 최대 수익(Max)보다 크다면, Max를 업데이트
			Max = ret;
	}

	Memo[Day] = Max; // Memo[Day]에 최대 수익(Max)을 저장하여 중복 계산을 피함
	return Memo[Day];
}


// 메인함수
int main() {
	// input
	input();

	// solve -> DP 실행
	int ret = getMoney(1);

	// output
	cout << ret;

	return 0;
}

---

4. 문제 풀이를 마치며..

백준 채점 결과, 혹시나 DFS를 돌려보니 역시나 터져버렸다.

블로그에 포스팅한 나의 첫 DP(다이나믹 프로그래밍) 문제이다.

 

한동안 기업 코테들에서 DP가 단골로 출제됐던 때가 있었다는데

요즘은 DFS, BFS, 그리고 시뮬레이션(구현) 문제가 단골이 되었다.

 

그래서 DP 유형의 문제들은 쳐다보지 않고 있었는데

점점 미뤄두다 보니 원래 못하던 것이 더욱 못해져가는 느낌이었다.

 

그래서 대표적인 DP 기본유형의 문제들을 풀어보며

연습해볼 생각이다.