[BOJ][Python3]14501.퇴사

문제 유형 : DP

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

 

문제 오답노트를 적어보겠다!! 풀이는 훌륭한 사람들이 일목묘연하게 정리한 포스트가 아주 많다. 풀이를 깊게 다루진 않을 예정이다.

우선 보자마자 그리디인지 DP인지 고민했지만 최적의 해를 구할 떄 subproblem으로 쪼갤 수 있다는 점에서 DP라고 판단했다.

 

그리고 문제 풀이 전략을 세웠는데, 바로 앞에서부터 뒤로 가며 문제를 풀었다. (심지어 table을 하나 더 만들었다.)

 

1차 풀이 접근은 다음과 같다.

 

간단하게 말하면 앞에서부터 살펴보며 들어갈자리 있으면 넣고, 없으면 넣는게 이득인지 아닌지 판별한다. 참고로 틀린 풀이다.

나름 빠르게 생각한 풀이고 타당하다고 생각, 테케도 통과해서 넣어봤지만 자꾸자꾸 오답이 떴다.

 

 

반례가 있겠거니 고심한 결과 다음과 같은 반례가 있었다…

 

문제를 틀리면 오답노트를 쓰는 게 정말 중요하다고 생각해서 답을 이해한 뒤에도 한참 동안 기존의 풀이는 왜 dp가 아니었는가를 고민했다.

문제는 subproblem으로 쪼갰을 때, i일차 이전 일차들과 i일차가 완벽하게 분리되지 않는다. 만약 i일차에 넣는 방법을 선택한다면 앞 일차에 공백이 생길 수 있고, 그 공백에 들어갈 수 있는 값을 dp 어레이가 반영해주지 못한다.

 

 

올바른 풀이 : 뒤에서부터 dp어레이를 만드는 방법

뒤에서부터 가면 i일차에 상담 일정을 잡는 경우, 잡지 않는 경우를 비교한다.

 

풀이의 가장 큰 차이점은 내 풀이에서 ‘상담에 걸쳐 있는 상태’가 존재한다. 뒤에서부터 접근하면 dp 어레이 자체에서 상담 했는지, 안했는지의 최적값을 가지고 있고 그 값을 갖다 쓰는데 문제가 없다.

 

하지만 내 풀이에서는 dp의 값을 재사용하기가 어렵다. 결국 dp의 값이 최선의 상태를 담고 있지 못한 탓이다.

 

접근은 비슷했던 게, i일차~끝까지만 있다고 생각한 상황에서 0일~(i-1)일은 없다고 하고 값을 구한 거다.

하지만 방향이 달랐던 건데, 앞→뒤인 상황에서는 0일~(i-1)일이 뒤에 영향을 미쳤기 때문에 사실상 0일~끝을 고려해야 말이 됐다. (aka 브루트포스)
하지만 뒤→ 앞인 상황에서는 0일~(i-1)일이 i일차~끝에 영향을 미치지 않는다. 그렇기 때문에 DP!

 

 

솔루션

def sol (table):
    dp = [0] * (len(table)+ 1)
    #0일차부터 시작

    # max(dp[i]) = i일차에 얻을 수 있는 maximum profit
    # dp[i] 는 i일차의 상담을 시작하거나 혹은 시작하지 않은 경우의 상담 상태다.

    for i in range(len(table)-1, -1, -1):

        appointment = table[i]
        times = appointment[0]
        profits = appointment[1]

        #만약에 초과하는 경우 넘겨준다
        if (i + times) > len(table):
            dp[i] = dp[i+1]
        else:
            dp[i] = max(profits + dp[i+times], dp[i+1])

    return max(dp)

day = int(input())
meeting_table = []

for _ in range(day):
    schedule = list(map(int, input().split()))
    meeting_table.append(schedule)

print(sol(meeting_table))