[Baekjoon][Python] 14501번 퇴사

14501번 퇴사

문제

풀이

문제를 분석하자면, DP를 이용하는 문제로, 반복문을 돌며 이전 값들을 이용하여 현재 날짜의 최대값을 택하는 문제이다.

주의할 점은 현재 날짜에서 1일을 초과하는 상담은 할 수 없다는 점이다. 예를 들어 1일 째 되는 날 5일짜리 상담을 할 수는 없는 것이다. 이러한 생각으로 각각의 날짜가 가장 최선인 값들을 찾아가면 문제를 해결할 수 있다.

위 생각에 기반하면, 오늘 할당된 상담이 1일을 초과하지 않는다면, 어제 상담이익 + 오늘 상담 이익이 답이 될 것이다. 하지만 또 하나 유의할 점은 이전 날들 중 오늘까지 딱 가능한 상담이 존재할 수 있다는 것이다. 무슨 말이냐면, 예를 들어 3일째 되는날 오늘 할당된 상담이 1일짜리에 상담이익이 10이고, 전날 상담 이익이 10이라면 합인 20이 답인 것처럼 보이지만, 만약 1일 째 되는날 할당된 상담이 3일이고 이익이 30이라면 1일 째 상담이 답이 된다. 즉, 3일 째 할당 된 상담을 하지 않고 1일 째 상담을 하는 것이 최대값이 된다는 것이다.

이러한 개념에 맞추어 코드를 작성하면 아래와 같다. 제일 먼저 당일에 상담이 가능하다면 전날 이익 + 오늘 이익을 dp에 넣어주고, 아니라면 전날 이익만 넣어준다. 그 이후 위의 개념대로 반복문을 돌리며 탐색한다.

import sys

input = sys.stdin.readline

N = int(input())
consulting = [(0, 0)]
dp = [0]

for _ in range(N):
    consulting.append(tuple(map(int, input().split())))
    
for i in range(1, N + 1):
    # 당일 상담 불가능
    if consulting[i][0] > 1:
        dp.append(dp[i - 1])
    # 당일 상담 가능
    else:
        dp.append(dp[i - 1] + consulting[i][1])
    for j in range(i - 1, 0, -1):
        if consulting[j][0] + (j - 1) == i:
            dp[i] = max(dp[i], consulting[j][1] + dp[j - 1])
        
print(dp[N])

결론

처음에 문제를 제대로 이해하지 못해 또 코드부터 짜다가 중간에 잘못된 것을 알고 아예 갈아 엎었었다. 항상 문제부터 똑바로 읽고 머리와 손으로 생각을 한 뒤 문제를 풀어야 한다. 성급하면 실수만 할 뿐이다.