알고리즘 :: 백준 :: Bruteforce :: 14501 :: 퇴사

문제

각 날짜에는 위와같이 상담 소요일과 수익이 나타난다. 주어진 상황에서 얻을 수 있는 최대 수익을 나타내시오.

문제접근

가장 기본적인 형태의 bruteforce 문제인데 스스로의 힘으로 풀지 못해서 너무 아쉽고 분했다...ㅠ

• 가장 기본적인 형태의 bruteforce 문제다.
• 각 날짜에 대해서 우리가 내릴 수 있는 결정은 선택한다와 선택하지 않는다이므로 총 시간복잡도는 $O(2^N)$이다.
• 0번 인덱스(1일) 부터 시작해서 선택하는 경우에 대한 재귀와 선택하지 않는 경우에 대한 재귀을 수행하고, 재귀의 결과가 기존의 결과보다 크다면 값을 갱신해주는 전략을 사용하고자 한다.

코드

#include <iostream>
using namespace std;

static int N, ans;
static pair<int, int> consult[15];

void solve(int day, int sum) {
	if (day > N) return;
	if (day == N && ans < sum) {ans = sum; return;}
	solve(day + 1, sum);		// 해당 날짜를 선택하지 않는 경우
	solve(day + consult[day].first, sum + consult[day].second);	// 선택하는 경우
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> consult[i].first >> consult[i].second;
	solve(0, 0);
	cout << ans << '\n';
}

결과