난이도 : ●●○ | 풀이 시간 : 30분 | 시간 제한 : 2초 | 메모리 제한 : 128MB | 기출 : 삼성전자 SW 역량테스트
문제
- 백준이는 N+1일에 퇴사하기 위해서 남은 N일 동안 최대한 많은 상담을 하려고 한다.
- 각각의 상담을 완료하는 데에 걸리는 기간 Ti, 상담을 하고 받을 수 있는 금액 Pi가 주어진다.
- 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하라.
입력조건
- 첫째 줄에 N(1<=N<=15)이 주어진다.
- 둘째 줄부터 N개의 줄에 Ti, Pi가 공백으로 구분되어 주어진다.
출력조건
- 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
입력예시
7
3 10
5 20
1 10
1 20
2 15
4 40
2 200
출력예시
45
아이디어
- 3일이 걸리는 1일 차 상담을 한다면 최대 이익은 '1일 차의 상담 금액 + 4일부터의 최대 상담 금액'이 된다.
- 이를 활용해서 뒤에서부터 거꾸로 구해나가면 된다.
- max(최대 상담 금액, dp[t[i]+i]+p[i])
코드
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)
# n-1번째부터 0번째까지
for i in range(n-1,-1,-1):
# 상담이 끝나는 시간을 계산
# 현재 시간 i + 이 상담에 걸리는 시간 t[i]
time = t[i]+i
# 상담이 시간안에 끝난다면
if time<=n:
# time일까지 받은 금액+이 상담을 해서 받는 금액과
# 기존 최대금액 중 더 큰 것으로 갱신
dp[i] = max(p[i]+dp[time],max_value)
# 최대금액 갱신
max_value = dp[i]
else:
# 상담이 시간안에 끝나지 않는다면 기존 최대금액을 그대로
dp[i] = max_value
print(max_value)
후기
- 처음에는 dp문제를 보면 어떻게 풀어야 하나 감이 안왔는데, 이제는 이거 냅색 알고리즘같은데..하는 데까지는 생각이 미쳐서 뿌듯하다.