[이코테] 다이나믹 프로그래밍 문제 - 퇴사 python

난이도 : ●●○ | 풀이 시간 : 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문제를 보면 어떻게 풀어야 하나 감이 안왔는데, 이제는 이거 냅색 알고리즘같은데..하는 데까지는 생각이 미쳐서 뿌듯하다.