[白駿DP]退社(python)
質問する
https://www.acmicpc.net/problem/14501
マイコード(答えを参照)
注釈はできるだけ詳しく書きますが、理解するのに時間がかかりました.
一般的なdp問題とは異なり,後から数えるとは考えにくい.
何度も解く必要がある.
https://www.acmicpc.net/problem/14501
マイコード(答えを参照)
"""
1. 아이디어
마지막 날부터 최선의 경우를 DP로 계산해준다.
2. 시간복잡도
O(2N) 정도?
"""
"""
일하는 날을 맨 뒤에서부터 계산해보자
7일을 선택하면 근무시간 초과로 이익 0
6일도 마찬가지
5일을 선택하면 이익 15
4일을 선택하면 이익은 20에, 5일에도 일할 수 있으므로 +15 해서 35
3일을 선택하면 이익은 10에 4일에도 일할 수 있으므로 (4일에 일하면 위에서 확인했듯이 5일도 일한다) +35 이므로 45
2일을 선택하면 이익은 20
1일을 선택하면 이익은 10에 4일부터 일할 수 있으므로 ( 아까 그 35 를 더한다) +35 이므로 45
결과적으로 1,4,5 일하면 45
또는 3,4,5 일하면 45
이 두가지의 경우가 최대이다.
"""
from sys import stdin
input = stdin.readline
n = int(input())
profit = [ list(map(int, input().split())) for _ in range(n) ]
dp = [0] * (n+1)
for i in range(n-1, -1, -1):
if profit[i][0] + i > n: # 근무시간을 초과한 경우
dp[i] = dp[i+1] # 현재 일을 하지 않는다
else:
# max(현재 일을 끝내고 현재 일을 끝낸 날에 쌓여있는 보상, 현재 일을 하지 않는 경우)
dp[i] = max(profit[i][1] + dp[i + profit[i][0]], dp[i+1])
print(dp[0])
に感銘を与える注釈はできるだけ詳しく書きますが、理解するのに時間がかかりました.
一般的なdp問題とは異なり,後から数えるとは考えにくい.
何度も解く必要がある.
Reference
この問題について([白駿DP]退社(python)), 我々は、より多くの情報をここで見つけました https://velog.io/@tyjk8997/백준-DP-퇴사pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol