BaekJoon 14501 퇴사

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

소스코드 1984 KB / 0 ms

출처 Baekjoon 

언어 C++ 17

분류 다이나믹 프로그래밍, 브루트 포스

 

설명

정말 부러운 상황에 있는 백준이가 퇴사를 하려한다, 상담 계획이 주어져 있을 때, 최대로 돈을 많이 벌 수 있는 금액을 출력해주자.

 

백준이가 퇴사 하기 전까지 최대한 많은 상담을 해야한다. 백준이가 돈을 더 벌기 위해서 일을 일부러 건너 뛰는 경우도 존재 한다.

또한 일을 하는 경우에 자신의 퇴사일이 지나는 경우에는 일을 받지 않아야 한다.

돈을 더 벌기 위해서 일을 하지 않아야 하는 경우와 퇴사일이 지나는 경우를 포함하면 총 3가지 경우가 존재한다.

DP로 구현하는 방법도 있지만 이번에는 브루트 포스를 이용해 보자

 

알고리즘

1. 백준이의 N일간 계획표를 입력 받는다.

2. 1일부터 N일까지 시작일은 무조건 일을 하는 경우로 판단해 탐색 함수를 실행한다.

 2 - 1. 다음 일하는 날이 퇴사일이 지나는지를 판별한다.

 2 - 2. 퇴사일이 지나는 경우 날짜만 추가해 재귀 함수를 호출한다. 지나지 않는 경우 현재까지의 총 금액 + 이번 금액을 추가해 재귀함수를 호출한다.

 2 - 3. 탐색하는 날짜에 일을 하지 않는 경우로 판단해 다음날 일 하는 경우의 재귀함수를 호출한다.

3. 최대값을 출력후 종료한다.

 

소스코드

#include <iostream>
using namespace std;

const int MAX = 15;

int n;
int max_earn;
int time[MAX];
int pay[MAX];
bool check[MAX];

void solution(int pos, int sum)
{
	if (pos < n)
	{
		int next = pos + time[pos];
		if (next <= n)
			solution(next, sum + pay[pos]);
		else
			solution(next, sum);
		solution(pos + 1, sum);
	}
	else
	{
		if (max_earn < sum)
			max_earn = sum;
	}
}

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> time[i] >> pay[i];

	for (int i = 0; i < n; i++)
		solution(i, 0);

	cout << max_earn;
	return 0;
}