[백준] 14501번 퇴사 파이썬 해설

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

14501번: 퇴사

부루트 포스, 다이나믹 프로그래밍 알고리즘으로 분류된 문제이다.

부루트 포스 알고리즘은 모든 경우를 다 비교해보는 무식한 알고리즘이라고 하는데 사실 다이나믹 프로그래밍과의 차이를 모르겠다.

 

풀이

---

나름 부루트 포스 알고리즘의 방향으로 접근해보려 했으나, 정답을 맞히고 보니 다이나믹 프로그래밍 알고리즘을 이용해서 문제를 해결하였다. 정말 무슨 차이인지 모르겠다.

우선 문제를 잘 이해하고 문제 풀이의 흐름을 정했다.

N이 주어지면 마지막  N일 부터 최대로 돈을 벌 수 있는 경우를 체크했다.

여기서 주의할 점은 N번째 날은 상담에 걸리는 시간이 1일을 넘어가면 상담을 하지 못한다.

이 조건만 주의해서 프로그래밍을 한다면 큰 문제없이 정답을 맞힐 수 있을 것이다!

 

-정답 코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    N = int(input())
    arr = []
    arr.append(())
    for i in range(N):
        t, p = map(int,input().split())
        arr.append((t, p))

    dp = [0 for _ in range(N+1)]

    for i in range(N,0,-1):
        temp = i + arr[i][0]
        if i == N:
            if arr[i][0] == 1:
                dp[i] = arr[i][1]
        elif temp == N + 1:
            dp[i] = max(arr[i][1], dp[i + 1])
        elif temp < N + 1:
            dp[i] = max(arr[i][1] + dp[temp], dp[i + 1])
        else:
            dp[i] = dp[i+1]
    print(dp[1])

6번째 줄에서 arr.append(())를 해 준 이유는 인덱스를 0부터 접근하는 게 아니라 1부터 접근해서 조금 더 가시성이 좋은 프로그래밍을 위해서 이다.

정답률이 높았던 알고 보면 쉬운 문제이다.

 

결과

---

사실 나는 몇 번의 시행착오 때문에 3번이나 틀렸던 문제이다..ㅎㅎ

블로그를 운영한 지 얼마 되지 않아서 나만의 프레임이 없다.

매번 새로운 프레임으로 예쁘게 정리해보려고 노력 중이다.