문제
나의 풀이
1. 탑다운..이 아니라 바텀업
n = int(input())
schedule = [list(map(int, input().split())) for _ in range(n)]
dp =[0]* (n + 1) # 최댓값을 담을 dp 테이블
for day in range(n - 1, -1, -1): # n일부터 거꾸로 세어나가며
t, p = schedule[day][0], schedule[day][1] # 소요 일수, 수입
if day + t <= n:
dp[day] = max(dp[day + 1], dp[day + t] + p) # 최대값 갱신
else:
dp[day] = dp[day + 1] # 그냥 지나침
print(dp[0])2. 바텀업으로도 풀어봐야지 나중에..가 아니라 그냥 실패
1) 실패
n = 7
schedule = [[3, 10], [5, 20], [1, 10], [1, 20], [2, 15], [4, 40], [2, 200]]
dp =[0] * (n) # 최댓값을 담을 dp 테이블
for day in range(n): #
t, p = schedule[day][0], schedule[day][1] # 소요 일수, 수입
if day + t < n:
dp[day + t] = max(dp[day + t - 1], dp[day + t] + p) # 최대값 갱신
elif day + 1 < n:
dp[day + 1] = dp[day] # 그냥 지나침
print('day', day, dp)
print(max(dp))- 예를 들어 3일짜리 일을 하게 되면, 그 3일 동안은 다른 일을 할 수 없는데, 바텀업으로 이를 구현하기가 넘나 어렵다. 그래서 위의 식도 언뜻보면 멀쩡해보이지만, 오류 투성이!
다른 사람 풀이
내 인생의 주연