[백준] C/C++ 퇴사 [삼성 SW 역량 테스트 기출 문제 ]

문제부터 보면 전형적인 DP 문제라고 생각이 든다. 하지만 문제에 시간초를 보면 2초나 주어진다. 그래서 이 문제를 DP로 풀어야만 하는가 의문이 들면서 접근을 했다.

 

우선 문제 풀이 생각으로는 시간 제한도 2초이고 입력 수도 1000인것을 감안해서 넉넉하기 때문에 1일부터 Ti 시간만큼 뛰어가면서 전부 더해보는 방식으로 했다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
int visited[1001];
vector<pair<int, int>> works;
int answer;
int pays;

void start(int x, int pre) {
	if (x == n) {
		answer = max(answer, pays);
		return;
	}
	if (x > n) {
		answer = max(answer, pays - works[pre].second);
		return;
	}

	for (int i = x; i < n; i++) {
		pays += works[i].second;
		start(i + works[i].first, i);
		pays -= works[i].second;
	}
}
int main() {
	cin >> n;
	int time, pay;

	for (int i = 0; i < n; i++) {
		cin >> time >> pay;
		works.push_back({ time, pay });
	}

	start(0,0);
	cout << answer;
}

만약 날짜가 딱 떨어지면 그때까지의 페이를 값으로 가지면 되고, 날짜가 오버가 되면 그 전까지의 페이를 갖기때문에 return 하는 조건을 2가지로 나누었다. 

사실 풀이 과정이 그렇게 마음에 들지는 않지만 다른 블로그들은 전부 DP로만 풀려있어서 이러한 방법도 있다는 것을 기록하려고 남겼다.