[백준] 14501번 퇴사 - C++ (Bruteforce, 재귀함수)

발상

1. 우선 알고리즘 중 bruteforce를 이용해야겠다고 생각했다. 1~N까지 날짜 중 되는 상담을 잡았을 때의 최대 값을 구하는 것이고, A일이라면 A+1일의 상담에 걸리는 날짜부터 N까지를 다시 탐색하는 방법으로 문제를 해결하면 될 것이라고 생각했다. 

2. 종료하는 분기점은 date가 N보다 클 때이다. 이 때 종료하고, 그 이전의 cost값을 v에 push해준다. 그런데 date=N+1일 때는 실제로는 직전에 시작한 상담이 마지막 날에 정확히 끝나는 것이므로, (예로, N이 7일 때, 5일에 3만큼의 상담을 했다면, date=8이 되어 종료되지만 실제로는 5, 6, 7일 3일간 상담을 하고 8로 넘어가므로 date=8도 유효한 값이다.) 이 때의 cost값도 v에 push해준 뒤 return하도록 한다. N+1보다 클 때에는 상담이 마지막 날을 지나야 끝나므로 유효하지 않은 경우이고 신경쓰지 않아도 된다. 

3. 그리고 재귀함수 부분이다. 현재 index인 date에서는 date 날짜부터 N일 전까지의 모든 상담을 고려해야 한다. 따라서 for문을 이용해 i=date부터 N까지의 경우를 고려하고, 상담하는 날짜인 i에서 i에 배치된 상담의 날짜를 더한 값을 다음 재귀함수의 날짜 값으로 넣어주고, cost의 경우 이전까지의 cost에 i에 배치된 상담의 가격을 더해 다음 재귀함수의 가격 값으로 넣어 준다. 

4. date와 cost값 두 개를 한 묶음으로 저장할 수 있는 pair 자료형을 이용했다. 

소스코드

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

using namespace std;

int N;
vector <int> v;
vector <pair <int, int>> input;

void bruteforce(int date, int cost){
	if (date>N){ 
		if (date==N+1) v.push_back(cost);
		return;
	}
	for(int i=date; i<N+1; i++){
		bruteforce(i+input[i-1].first, cost+input[i-1].second);
		v.push_back(cost);
	}
}
int main(){
	cin >> N;
	for(int i=0; i<N; i++){
		int temp1, temp2;
		cin >> temp1 >> temp2;
		input.push_back(make_pair(temp1, temp2));
	}
	bruteforce(1, 0);
	sort(v.begin(), v.end());
	cout << v[v.size()-1];
}

재귀함수 부분만 따로 살펴보면 다음과 같다.

void bruteforce(int date, int cost){
	if (date>N){ //N보다 크면 종료  
		if (date==N+1) v.push_back(cost); //단, N+1일에서 끝난 경우는 상담이 N일에 종료된 경우라 포함 
		return;
	}
	for(int i=date; i<N+1; i++){ //현재 날짜(전 단계에서 상담이 끝난 다음날)부터 N까지 모든 상담 고려 
		bruteforce(i+input[i-1].first, cost+input[i-1].second); //재귀함수: 고려하는 날짜+해당 날짜 상담일수, 이전까지 가격+해당날짜 가격 
		v.push_back(cost);// 종료된 이전 단계 저장하고 반복문 다음 단계로 
	}
}

재귀함수에 넣는 인자 값을 잘못 설정해 처음엔 틀리게 나왔지만 수정했고 올바른 알고리즘을 떠올려서 문제를 풀었다. 

조금 더 연습하면 재귀함수 활용한 문제도 더 잘 풀 수 있게 될 것 같다.

어떤 인자를 넣어야 함수가 제대로 돌아가는지를 잘 생각하고, 작성한 대로 함수를 돌렸을 때 예외가 되거나 고려되지 않는 경우는 없는지를 다시 생각해주어야 할 거 같다.

 

+) 문제 알고리즘을 보니 DP도 있던데 DP 활용해서도 풀어보면 좋겠다.