[백준 15486번 C/C++] 퇴사2

 

[백준 15486번 C/C++] 퇴사2

 

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

15486번: 퇴사 2

---

 

해결전략

 

동적계획법 Dynamic Programming, DP

 

---

 

처음 시도한 코드 - 시간초과

 

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

int n;
int total;
vector<int> T, P;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	T.resize(n + 1); P.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> T[i] >> P[i];
	}

	vector<int> dp(n + 1, 0);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < i; j++) 
		{
			if (j + T[j] == i)
				dp[i] = max(dp[i], dp[j] + P[j]);
		}
		dp[i] = max(dp[i], dp[i - 1]);
	}

	cout << dp[n] << "\n";

	return 0;
}

 

 

 

---

 

정답코드

 

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

int n; // 상담할 수 있는 날짜 수
vector<int> T, P;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;  
	T.resize(n + 1); P.resize(n + 1);  
	vector<int> dp(n + 2, 0); // i일까지의 최대 이익을 저장할 벡터

	for (int i = 1; i <= n; i++) {
		cin >> T[i] >> P[i];  // 각 상담의 소요 시간과 이익을 입력
	}

	int max_value = 0;  // 이전까지의 최대 이익을 저장할 변수를 초기화
	for (int i = 1; i <= n + 1; i++) 
    {
		max_value = max(max_value, dp[i]);  // 이전까지의 최대 이익을 업데이트
		if (i + T[i] <= n + 1) {
			// i일에 상담을 시작하여 상담이 끝나는 날(i + T[i])에 대해 
			// 그전까지의 최대 이익(max_value)과 i일의 상담을 통해 얻을 수 있는 이익을 더한 값과 
			// 기존에 계산된 i + T[i]일의 최대 이익을 비교하여 더 큰 값으로 업데이트
			dp[i + T[i]] = max(dp[i + T[i]], max_value + P[i]);
		}
	}

	cout << max_value << "\n";  // 최대 이익을 출력

	return 0;
}

 

 

 

 

---