[BOJ]14501번: 퇴사 (c++)

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

14501번: 퇴사

 

방법 1 : 백트랙킹

#include <iostream>
#include <vector>

using namespace std;

int max_sum;

void dfs(vector<int> &dates, vector<int> &money, int sum, int index)
{
	// 일의 종료 시점이 주어진 날짜보다 클때
	if (index > dates.size())
	{
		return;
	}
	// 주어진 날짜에 일을 종료할 수 있을 때
	else if (index == dates.size())
	{
		if (max_sum < sum)
		{
			max_sum = sum;
		}
		return;
	}

	// index일에 들어온 일감을 선택할 때
	dfs(dates, money, sum + money[index], index + dates[index]);

	// index일에 들어온 일감을 선택하지 않을 때
	dfs(dates, money, sum, index + 1);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	int N;
	cin >> N;

	vector<int> dates(N);
	vector<int> money(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> dates[i] >> money[i];
	}
	
	// dfs - 백트랙킹으로 일감 조합
	dfs(dates, money, 0, 0);

	cout << max_sum;

	return 0;
}

 

방법 2: 백트랙킹 + 리턴값 활용 + 가지치기 추가(메모이제이션)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 15;
int N;
int time[MAX];
int pay[MAX];
int max_sum[MAX];

int go(int day)
{
	// 불가능한 근무 일때
	if (day > N)
	{
		return -987654321;
	}
	// 가능한 근무 일때
	if (day == N)
	{
		return 0;
	}
	// day의 최대값이 정해졌을 때
	if (max_sum[day] > 0)
	{
		return max_sum[day];
	}

	// day일에 들어온 상담을 하는 경우
	int sum1 = go(day + time[day]) + pay[day];
	
	// day일에 들어온 상담을 하지 않는 경우
	int sum2 = go(day + 1);

	// max_sum[day]에 최대값 저장 및 리턴
	return max_sum[day] = max(sum1, sum2);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> time[i] >> pay[i];
		max_sum[i] = -1;
	}

	// 최대 이익 출력
	cout << go(0);

	return 0;
}

 

암호 만들기 문제와 비슷하다

 

다음번 선택할 수 있는 일감의 index는

이전 일감이 끝나고 다음 날짜라는 점만 조심하면 된다.