[백준] 14501번 : 퇴사

문제

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

풀이

[백준] 14501번 : 퇴사 🥈(실버3)

• [알고리즘 : DP(동적 계획법)] 🔥

<✅ 문제 요약>
0. 상담 일정표는 상담 기간과 상담 금액으로 이루어져 있다.
1. N일 동안 적절한 상담 조합을 통해 구할 수 있는 최대 금액을 출력한다.

<✅ 풀이방법>

0. 크기가 N 인 DP 배열 생성
1. 당일 상담이 퇴사 전에 가능할 경우 상담 선택
2. 당일 상담이 끝나는 날 중 보상이 가장 큰 날의 보상을 당일 보상에 더한다.
3. DP 배열에서 가장 보상이 큰 날을 return

코드(code)

import sys
input = sys.stdin.readline

def solution():
    N = int(input())
    # [상담일, 금액]
    # [[3,10],[5,20],[1,10],[1,20],[2,15],[4,40],[2,200]]
    schedule = [list(map(int,input().split())) for i in range(N)]  
    # N일동안 선택할 수 있는 최대 금액
    dp = [0]* N


    for i in range(N):
        if i+schedule[i][0]<=N:
            dp[i] = schedule[i][1]
            for j in range(i):
                # 이전 상담이 오늘 전에 가능할 경우
                if j + schedule[j][0] <= i :
                    # 이전 상담 금액 + 당일 상담 금액의 최대값 선택
                    dp[i] = max(dp[i], dp[j]+schedule[i][1])
    return max(dp)
print(solution())

회고

• DP을 통해서 문제를 풀었는데 해당 문제를 DP으로 생각하고 접근하는게 까다로웠다.
• DP인 근거는 해당 문제는 결국 이전의 금액들을 비교하면서 앞의 값을 여러 번 구한다는점에 있었다.

• [해당 코드]

  https://github.com/joejames0830/ps_study/blob/main/DP/14501(%ED%87%B4%EC%82%AC).py