반응형
https://www.acmicpc.net/problem/14501
n = int(input())
data = []
for i in range(n):
time, benefit = map(int, input().rstrip().split())
data.append((time, benefit))
dp = [0] * (n + 1)
max_value = 0
for i in range(n - 1, -1, -1):
if i + data[i][0] <= n:
dp[i] = max(dp[i + data[i][0]] + data[i][1], max_value)
max_value = dp[i]
else:
dp[i] = max_value
print(max_value)
이 문제는 뒤쪽 날짜부터 거꾸로 확인하면서 DP 테이블을 갱신해나가는 다이나믹 프로그래밍 아이디어로 풀 수 있다.
문제의 예를 통해 보면 1일차에 상담을 진행하는 경우 최대 이익은 '1일차의 상담 금액 + 4일차부터의 최대 상담 금액'이 된다. 이러한 원리를 이용하여 뒤쪽 날짜부터 거꾸로 계산하며 문제를 해결할 수 있다.
'dp[i] = i번째 날부터 마지막 날까지 낼 수 있는 최대 이익'이라고 하면 코드로는 다음과 같이 나타낼 수 있다.
dp[i] = max(dp[i + data[i][0]] + data[i][1], max_value)
느낀 점
뒤쪽 날짜부터 확인한다는 아이디어를 떠올리는 것이 쉽지 않았다. 따라서 또 다른 방법으로 풀 수 있을까 하여 다른 블로그들을 많이 찾아본 결과 문제에서 N의 범위가 15밖에 안돼서 완전 탐색으로도 문제를 풀 수 있다는 점을 알고 완전 탐색으로도 다시 풀어보았다.
n = int(input())
data = []
for i in range(n):
time, benefit = map(int, input().rstrip().split())
data.append((time, benefit))
max_value = 0
dp = [0] * n
for i in range(n):
if data[i][0] + i > n:
continue
dp[i] = data[i][1]
for j in range(i):
if data[j][0] + j > i:
continue
dp[i] = max(dp[i], data[i][1] + dp[j])
max_value = max(max_value, dp[i])
print(max_value)
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 12015 - 가장 긴 증가하는 부분 수열 2 (0) | 2022.02.15 |
---|---|
[BOJ] 18353 - 병사 배치하기 (0) | 2022.02.14 |
[BOJ] 2110 - 공유기 설치 (0) | 2022.02.06 |
[BOJ] 1654 - 랜선 자르기 (0) | 2022.02.02 |
[BOJ] 2108 - 통계학 (0) | 2022.01.28 |