[백준 c++] 14501 퇴사 (실3)

📌 문제

N일이 주어지만 하루 별 해결할 수 있는 일이 주어진다.

해당 일이 언제 주어지는지와 그 일을 해결하기 까지 필요한 시간이 주어진다.

주어진 일 리스트에서 일을 골라 했을 때 가장 수입이 높을 때의 수입을 출력하는 문제다.

 

문제를 처음 봤을 땐 백트래킹 문제인가? 싶었는데

최종 결과를 이전에 판단할 수 없기 때문에 brute force 문제라고 판단했다. 

1년전, 동기들이랑 코딩테스트 스터디를 했을 때 풀었는 듯 하다...

과거에 내가 모든 경우의 수를 탐색할 수 있도록 재귀 함수를 기반으로 구현을 했다. 1년전 코드기 때문에 부끄럽다...

 

사실, 재귀함수는 위험한 방법이고 불필요하게 프로세스를 생성하므로 백준 문제를 풀 때 자주 시간초과가 났기 때문에

내 코드가 그렇게 좋은 방법은 아닌 듯 하다. 물론 C++는 시간복잡도 깡패기 때문에 재귀로 문제를 작성해도 충분히 통과가 가능했다...ㄷㄷ

참고로 말하면, 나 제외 다른 친구들은 python으로 DP 사용하지 않고 제출하면 시간 초과가 뜬다고 한다.

python이 느린건지 C++이 느린건지....

 

 

💻 정답 코드

/*
	2021 - 03 - 20 <brute-force>
	beakjun 14501
	KangYoungSeo

	반복문 2개 => O(N^2)
*/
#include <iostream>
using namespace std;

int time[16];
int pay[16];
int N;

int recursive(int idx) {

	if(idx > N) return 0;
	int FF = recursive(idx + 1);

	if (idx + time[idx] > N + 1) return FF;
	
	int TT = pay[idx] + recursive(idx + time[idx]);
	return TT > FF ? TT : FF;
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
		scanf("%d %d", &time[i], &pay[i]);

	//using recursive function, search all of cases, and find max

	int max = recursive(1);
	printf("%d", max);
	return 0;
}

⏱ 결과