197. 퇴사
1. 다이나믹 프로그래밍
n = int(input())
t = []
p = []
dp = [0] * (n + 1)
max_value = 0
for _ in range(n):
x, y = map(int, input().split())
t.append(x)
p.append(y)
#리스트를 뒤에서부터 거꾸로 확인
for i in range(n - 1, -1, -1):
time = t[i] + i
#상담이 기간 안에 끝나는 경우
if time <= n:
dp[i] = max(p[i] + dp[time], max_value)
max_value = dp[i]
else:
dp[i] = max_value
print(max_value)
2. C++
#include <bits/stdc++.h>
using namespace std;
int n; // 전체 상담 개수
vector<int> t; // 각 상담을 완료하는데 걸리는 기간
vector<int> p; // 각 상담을 완료했을 때 받을 수 있는 금액
int dp[16]; // 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
int maxValue;
int main(void) {
cin >> n;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
t.push_back(x);
p.push_back(y);
}
// 리스트를 뒤에서부터 거꾸로 확인
for (int i = n - 1; i >= 0; i--) {
int time = t[i] + i;
// 상담이 기간 안에 끝나는 경우
if (time <= n) {
// 점화식에 맞게, 현재까지의 최고 이익 계산
dp[i] = max(p[i] + dp[time], maxValue);
maxValue = dp[i];
}
// 상담이 기간을 벗어나는 경우
else dp[i] = maxValue;
}
cout << maxValue << '\n';
}
Author And Source
이 문제에 관하여(197. 퇴사), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@corone_hi/197.-퇴사저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)