15486

날짜 : 2023. 06. 11

사용 언어 : python

 

문제

https://www.acmicpc.net/problem/15486

 

 

코드

import sys

n = int(sys.stdin.readline())
con = []
for _ in range(n):
    con.append(list(map(int, sys.stdin.readline().split())))  # 입력

dp = [0] * (n + 1)
for i in range(n-1, -1, -1):  # 역순으로 진행
    dp[i] = dp[i + 1]  # 값 미리 받아옴
    if con[i][0] + i > n: continue  # 일자 초과
    if dp[i + 1] < dp[i + con[i][0]] + con[i][1]:  # 해당 날짜 상담 했을 때와 안했을 때 비교
        dp[i] = dp[i + con[i][0]] + con[i][1]  # 상담을 하는 경우
    else:
        continue  # 상담을 하지 않는 경우 pass

print(dp[0])

 

 

풀이

- 전형적인 DP문제이다.

- 조건에 따라 입력받은 후 dp를 실행한다.

- 역순으로 진행하고, 우선적으로 다음날의 최대 임금을 받아온다.

- 그 다음 해당 일자의 상담을 진행했을 때의 케이스와 진행하지 않았을 때의 케이스를 비교한다.

- 비교하는 과정에서 해당 상담 일자의 소요날짜(con[i][0])를 가져와 상담을 하지 않았을 때의 최대 임금(dp[i + 1])과 상담을 했을 때의 최대 임금(dp[i + con[i][0]])을 비교한다.

- 상담했을 때의 최대 임금은 (해당 날짜에서 상담했을 때 완료된 날짜의 최대임금) + (상담 진행 시 받는 임금)이다.

- 역순으로 쭉 진행하고 값을 출력

 

 

알게된 점

- 0에서 정순으로 진행하려 했지만 풀이가 떠오르지 않아 역순으로 메모이제이션했다.

- 기존에 받았던 상담 기록을 어떻게 최신화할지 생각하다가 상담이 완료되는 시기와 상담을 하지 않았던 시기에서 아이디어를 떠올릴 수 있었다.

- 다만 테케는 전부 맞았는데 계속 1%에서 틀리길래 스터디원분한테 코드를 주고 물어봤더니 dp[i]값을 미리 dp[i + 1]값으로 설정한다면 날짜가 오버되면 곧바로 continue되기 때문에 값이 이상해질 수 있다는 힌트를 받을 수 있었다.

 

 

참고 사이트

-