[BOJ][백준 14501] 퇴사 - C++

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

14501번: 퇴사

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

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

---

0. 문제 읽기

다음과 같이 상담 일정표가 입력으로 주어진다.

• N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
• 상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다.
• 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성.

---

1. 문제풀이 아이디어

• 최댓값을 구해야하므로 DFS로 풀자.
• DFS에서 다음 스택으로 넘어가는 것은 두가지 분기, 이 날 일을 할지, 말지로.
• N+1에 도달하면 최댓값 계산해주자.

---

2. 코드 핵심 부분

1) DFS 함수,

   기본적인 DFS 함수이고 아이디어 대로 작성하였다.

   일을 할지 말지 두 분기로 나누는 것이 포인트였다.

// DFS함수, 아이디어대로 구현하였다.
void dfs(int Day, int Sum) {

	if (Day > N) {

		if (Sum > Ans)
			Ans = Sum;

		return;
	}

	// 이 날 일을 한다! (단, 가능해야함)
	if (Day + Scdl[Day][0] <= N+1)
		dfs(Day + Scdl[Day][0], Sum + Scdl[Day][1]);

	// 이 날은 일을 안한다!
	dfs(Day + 1, Sum);
}

---

3. 전체 코드

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

using namespace std;

/*
1. 문제읽기
	N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
	상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다.
	상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성.
*/

/*
2. 아이디어
	최댓값을 구해야하므로 DFS로 풀자.
	DFS에서 다음 스택으로 넘어가는 것은 두가지 분기, 이 날 일을 할지, 말지로.
	N+1에 도달하면 최댓값 계산해주자.
*/

// 필요 인자들
int N; // 상담기간 (1 ≤ N ≤ 15)
int Scdl[1001][2]; // 상담 스케쥴, 1일부터 저장
int Ans;

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

// DFS함수, 아이디어대로 구현하였다.
void dfs(int Day, int Sum) {

	if (Day > N) {

		if (Sum > Ans)
			Ans = Sum;

		return;
	}

	// 이 날 일을 한다! (단, 가능해야함)
	if (Day + Scdl[Day][0] <= N+1)
		dfs(Day + Scdl[Day][0], Sum + Scdl[Day][1]);

	// 이 날은 일을 안한다!
	dfs(Day + 1, Sum);
}

// 메인함수
int main() {

	// input
	input();

	// solve -> DFS 함수 실행, Day 1부터
	dfs(1, 0);

	// output
	cout << Ans;

	return 0;
}

---

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

채점 결과

사실 워낙 단순한 기본 DFS 문제라 포스팅 해야할지 고민이었다.

 

그래도 포스팅한 이유는,

SSAFY 입사전만 해도 if랑 for로 모든 코드를 짜던 내가 어느새

DFS는 자동으로 구현하고 실버3 문제는 정말 쉽게 풀어내는 발전이 보여서 포스팅 한 문제이다.