[백준 14501] 퇴사

문제 출처: https://www.acmicpc.net/problem/14501

풀이

재귀함수 사용을 많이 어려워하는데, 아이디어는 알겠는데 구현력이부족해서 다른분들의 코드를 참고했습니다.

재귀함수를 사용하여 모든 케이스를 탐색해보는 방법을 사용했습니다.

나올수있는 경우는 1. 오늘 상담하고, 상담한 날만큼 건너뛰기 2. 상담안하고 하루 건너뛰기가 있습니다. 이것을 재귀로 구현해주면됩니다.

모든경우를 탐색하므로, 하루 건너뛰기를 수행하는 함수는 사실상 하루 이상의 day들을 건너뛴다고 할 수 있습니다.(이걸몰라서....)

코드

#include<iostream>
#include<algorithm>
using namespace std;
int t[16];
int p[16];
int n, max_val;
void func(int day,int profit);
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> t[i] >> p[i];
	//day=1일,이익0으로시작
	func(1, 0);
	cout << max_val << endl;
}
void func(int day,int profit)
{
	//탈출조건
	if (day > n + 1)return;
	//day==n+1이면max값 갱신후 종료(답)
	if(day==n+1)
	{
		max_val = max(max_val, profit);
		return;
	}
	//두가지 case

	//1. 오늘 상담하고,상담한 날만큼 건너뛰기
	if (day + t[day] <= n + 1)
	//두번째인자의, +p[day]해주는이유는 profit이 누적이고, p[day]가 그 날의 이익이므로
		func(day + t[day], profit+p[day]);
	//상담안하고 넘어간다.
	if (day + 1 <= n + 1)func(day + 1, profit);
}

결과