[백준] 14501번 퇴사 - 파이썬

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

14501번: 퇴사

---

sol) 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램 ⇒ 상담할 수 있는 모든 경우의 수를 구해 최대수익 결과 return

 

 

1. 첫째줄에 n , 둘째 줄부터 상담을 완료하는데 걸리는 기간(T)과 상담을 했을 때 받을 수 있는 금액(P) 받아오기

n = int(input())
profit = [list(map(int,input().split())) for _ in range(n)]

 

2. 상담을 하는 경우와 안하는 경우 모든 경우의 수 계산 (재귀 사용)

 

• 만일 2일에 잡혀있는 상담이 총 t만큼 걸린다고 하면 다음 상담은 t+2일부터 가능하다 

def recur(idx, p) :

    #해당 일에 상담을 하는 경우 
    recur(idx + profit[idx][0] , p + profit[idx][1])
    #해당 일에 상담을 하지 않을 경우
    recur(idx + 1 , p )

3. 예외적용하기 

• 만일 7일에 잡혀있는 상담이 2일이 걸리는 상담이라면 퇴사일을 넘어서므로 상담을 할 수 없다
• 즉, 상담이 잡혀 있는 날 + 상담을 하는데 걸리는 기간(idx)이 퇴사일(n)을 넘어서면 안된다

def recur(idx, p ) :
	global answer 
    
  	if idx >= n :
    	#만일 퇴사일을 넘어설 경우 결과 X 
        	if idx > n :
        		return
    	#최대 수익일 경우 업데이트 
        answer = max(answer , p) 
        return answer
    
    #해당 일에 상담을 하는 경우 
    recur(idx + profit[idx][0] , p + profit[idx][1])
    #해당 일에 상담을 하지 않을 경우
    recur(idx + 1 , p )

 

4. 전체코드 작성 

 

def recur(idx, p ) :
	global answer 
    
  	if idx >= n :
    	#만일 퇴사일을 넘어설 경우 결과 X 
        	if idx > n :
        		return
    	#최대 수익일 경우 업데이트 
        answer = max(answer , p) 
        return answer
    
    #해당 일에 상담을 하는 경우 
    recur(idx + profit[idx][0] , p + profit[idx][1])
    #해당 일에 상담을 하지 않을 경우
    recur(idx + 1 , p )
    
n = int(input())
profit = [list(map(int,input().split())) for _ in range(n)]

answer = 0 
recur(0,0)
print(answer)

---

탑다운 DP 방식 

n = int(input())
interview = [list(map(int,input().split())) for _ in range(n)]
#계산된 결과를 저장하기 위해 dp 초기화 
dp = [-1 for _ in range(n)]

def recur(idx) : 

    if idx == n-1 : #마지막 일자에 끝나면 0반환
        return 0
    if idx > n :
        return -99999

    #상담을 하는 경우 와 안하는 경우 중 더 많은 돈을 버는 경우를
    #dp 테이블에 저장하겠다 (큰 값을 dp[idx]로 저장)
    dp[idx] = max(recur(idx + interview[idx][0]) + interview[idx][1], recur(idx+1) )

    return dp[idx]

recur(0)
print(dp)