[알고리즘][파이썬]14501-퇴사

문제 

 

1. 초기 풀이

import sys

N = int(sys.stdin.readline())
li = [list(map(int,sys.stdin.readline().strip().split())) for _ in range(N)]

s =[0]
for i in range(N-1,-1,-1):
    S = li[i][0]
    M = li[i][1]
    MAX = M
    if(i+S-1)>=N:
        li[i][1] = -1
        continue
    for j in range(i+S,N):  #해당 일자의 상담기간 이후 기간을 for문으로 돌면서 최대 금액을 찾는다. 
        if(li[j][1] != -1 ):
            MAX = max(MAX, M + li[j][1])  
            
    li[i][1] = MAX  #각 일자별 최대 금액으로 list를 갱신한다.  
    s.append(li[i][1])


print(max(s))

초반 풀이에서는 DP를 사용하지 않고 풀었다. 

각 일자별로 최대의 수입을 기재해 놓고 모든 일자 중에 최댓값을 출력하게 코드를 작성했다. 

각 일자별 최대수입은 s 리스트를 따로 선언해서 append후 max() 함수를 사용했다.

 

😅발생한 오류  

s에 0으로 초기화하지 않아 N =1일 경우의  런타임에러(ValueError)이 발생했다. 

ValuError은 잘못된 값이 들어갔을 때 발생하는 오류 이다. 

N =1일 경우 s가 빈리스트인채로 max() 함수에 들어가게 돼서 오류가 발생한 것이다. 

다양한 반례를 고려해서 초기화에 주의를 해야할 것 같다. 

 

이 문제를 dp를 이용하여 풀이하면 더 간단한 코드를 구현할 수 있다. 

 

2.DP 풀이

import sys


N = int(sys.stdin.readline())
li = [list(map(int,sys.stdin.readline().strip().split())) for _ in range(N)]
dp = [0 for _ in range(N+1)]

for i in range(N-1, -1, -1): 
    if i + li[i][0] > N: # 상담에 필요한 일수가 퇴사일을 넘기면
        dp[i] = dp[i+1] # 다음날 값을 가져온다. 
    
    else:
        dp[i] = max(dp[i+1], dp[i + li[i][0]] + li[i][1]) # 오늘 상담을 안 할 경우와 상담을 할 경우 중 max 값

print(dp[0])

 

❗처음에 dp 배열을 선언해 줄 때 N+1크기로 선언해 주는 것을 주의해야 한다. 

상담에 필요한 일수가 퇴사일을 넘기는 경우 다음날의 값을 가져오도록 코드를 구현했는데 

마지막날(N번째)이 이에 해당한다면 가상의 다음날(N+1)이 필요하기 때문이다. 

 

DP
-다이나믹 프로그래밍(동적 계획)
-하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용
-큰 문제를 작은 문제로 쪼개서 그 답을 저장해 두고 재활용

 

 

+또 다른 DP문제👍

[알고리즘][파이썬]1149-RGB거리