https://www.acmicpc.net/problem/14501
보자마자 DP인건 알아챘는데 점화식 세우는데 오래 걸렸다..
문제 예제를 보면 6, 7일 같은 경우 N을 벗어나기 때문에 포함시킬 수 없다. 이 조건을 보고 역순으로 풀어야겠다고 판단했다. (근데 앞에서부터 풀어도 된다.)
뒤에서부터 오는데 만약 인덱스 + time이 N을 넘어가면 dp[i] = dp[i+1]을 해주었다.
처음에는 dp[i] = 0을 했는데, 이렇게 되면 time이 1일 때도 0으로 되기 때문에 틀린다.
ex) n = 7일 때,
만약 6일에 하는 미팅이 이틀 걸리면 퇴사 날짜를 넘기기 때문에 못한다. 근데 7일에 하는 미팅이 하루 걸리는 거면 포함시켜야 한다. 이를 포함시키는 코드가 아래와 같다.
이 코드를 처음에는 dp[i] = 0으로 구현했다가 포함시킬 수 있는 미팅까지 없애버려서 최대 이득이 안 나왔다..
그 이후에는 점화식을 작성해서 풀면 된다. 그날 미팅하고 이후 미팅을 하는 게 이득인지, 아니면 앞에서 더해온 dp 값이 이득인지 판단했다.
dp[i+schedules[i][0]]은 미팅 소요 날짜를 더해준 거다. 만약 첫 번째 미팅을 했는데 3일 걸린다면 3일 후인 네 번째 미팅을 더해준 거다.
이때 schedules[i]의 0번째 인덱스는 소요 시간이고, 1번째 인덱스는 돈이다.
정답 코드
import sys
input = sys.stdin.readline
n = int(input())
schedules = []
for _ in range(n):
time, money = map(int, input().split())
schedules.append([time, money])
dp = [0 for _ in range(n+1)]
for i in range(n-1, -1, -1):
if i + schedules[i][0] > n:
dp[i] = dp[i+1]
else:
dp[i] = max(dp[i+1], schedules[i][1] + dp[i+schedules[i][0]])
print(dp[0])
'PS > 백준' 카테고리의 다른 글
[백준] 14889번 스타트와 링크 (python) (0) | 2024.07.07 |
---|---|
[백준] 14888번 연산자 끼워넣기 (python) (0) | 2024.07.07 |
[백준] 13458번 시험 감독 (python) (0) | 2024.07.07 |
[백준] 1021번 회전하는 큐 (python) (1) | 2024.07.02 |
[백준] 10866번 덱 (python) (0) | 2024.07.02 |