[백준] 14501 퇴사 파이썬 python

문제링크

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

14501번: 퇴사

 

코드

1) 브루트포스

from ast import AnnAssign
import sys
input = sys.stdin.readline
 
n = int(input())
day = [0]*n
pay = [0]*n
ans = 0
 
for i in range(n):
    day[i], pay[i] = list(map(int, input().split()))
 
def go(d, tot):
    global ans
    if d==n: #퇴사일
        if ans<tot: ans = tot
        return 
    if d>n:
        return #퇴사일 초과하여 불가
    go(d+day[d], tot+pay[d]) #해당 d 선택
    go(d+1, tot) #선택X
    
go(0,0)
print(ans) 
 

 

2) DP

from ast import AnnAssign
import sys
input = sys.stdin.readline
 
inf = 10**9
n = int(input())
day = [0]*n
pay = [0]*n
tot = [-1]*n
 
for i in range(n):
    day[i], pay[i] = map(int, input().split())
 
def go(d):
    if d==n:  #퇴사일
        return 0 
    if d>n:  #퇴사일 초과하여 불가
        return -inf 
    if tot[d]!=-1: #이미 구해진 값으로, memoization활용
        return tot[d]
        
    t1 = pay[d] + go(d+day[d]) #해당 d 선택
    t2 = go(d+1)               #선택X
    tot[d] = max(t1,t2)
    return tot[d]
 
print(go(0)) 
 

 

POINT

1) 브루트 포스 접근

d번째 상담을 선택할 건지 말건지를 코드로 구현해야한다. ==> 시간 복잡도 O(2^n)

 

2) DP로 접근

큰 문제의 정답을 작은 문제를 활용하여 구할 수 있다.

예를들어, 4일이 된 경우 : (1~3일까지 상담 최대 수익) +  (4~n일 최대 수익) 으로 나누어 구할 수 있다

 

'tot[d] : d일이 된 이후로부터 얻을 수 있는 최대 수익'으로 정의한다. 

d번째 할 수 있는 행동 2가지 : 1) d번째 선택하기 2) d번째 선택하지 않음

 

tot[d] = max( d번째 선택하고 + 그다음 가능한 날(d+day[d])에서부터의 최대 수익 = pay[d] + go(d+day[d]) ,

                    d번째 선택안하고, 바로 다음날로부터의 가능한 최대수익 = go(d+1) )

 

* 오류 : local variable 'ans' referenced before assignment

이유 : python 전역 변수 데이터를 확인은 가능하나, 수정은 불가하다.

해결방법: 함수내에서 사용시, global ans와 같이 전역변수 선언을 해주어야한다.