[백준] 15486번 퇴사 2 C++ 문제풀이

https://www.acmicpc.net/problem/15486

15486번: 퇴사 2

문제 풀이

DP를 통해서 문제를 해결하려고 했다.

dp[i]에는 i-1날까지 끝낼 수 있는 상담을 통한 최대수익을 저장했다.

첫번째로 현재 dp값이 이전 dp값의 최대보다 작은 경우 갱신해주고, 

두번째로 그 날 맡은 상담을 할 수 있는지, 아니면 N보다 커서 상담이 불가능한지를 고려하여 코드를 작성했다.

남들이 작성한 코드가 시간이 적게 걸린 것 봐서는 다르게 짜는 최적 코드가 존재하는 것 같다.

 

소스 코드

#include <iostream>
using namespace std;

int consult[1500001][2] = {0};
int dp[1500001] = { 0 };

int main() {
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> consult[i][0] >> consult[i][1];
	}

	int current_max = 0;
	dp[0] = 0;
	for (int i = 1; i <= N; i++) {
		// 현재 dp값이 이전 dp값의 최대보다 작은 경우 갱신
		if (dp[i] > current_max) {
			current_max = dp[i];
		}
		else {
			dp[i] = current_max;
		}
		// next_day = 상담 끝나는 날
		int next_day = i + consult[i][0];
		if (next_day > N + 1) {
			continue;
		}
		else {
			if (dp[next_day] < dp[i] + consult[i][1]) 
				dp[next_day] = dp[i] + consult[i][1];
		}
	}

	int max_num = 0;
	for (int i = 1; i <= N + 1; i++) {
		max_num = max(max_num, dp[i]);
	}
	cout << max_num << '\n';
}