08/27 퇴사 BOJ 14501 파이썬

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

14501번: 퇴사

 

두가지 방법으로 풀 수 있다.

1. 동적 계획법

2. DFS(깊이 우선 탐색법)

 

1. 동적 계획법

    - 메모이제이션을 i번째 상담을 수행했을 때 받을 수 있는 최대 페이를 기준으로 수행한다.

    - i 번째 상담을 수행하면 T[i] ( i번째 상담의 상담기간 ) 동안 상담을 하지 못하기 때문에 i부터 i +T[i] 사이에 있는 상담은

       뛰어넘는다.

    - i 번째 상담을 수행하려면 i번째 날부터 상담기간을 더한 날이 퇴사 날(i + T[i])을 넘지 않아야한다.

    -  i 번째 상담을 수행했을 때 퇴사날을 지나친다면 전날 값(dp[i-1]) 로 업데이트 하고 아니라면  전날 값(dp[i-1]) 과

       i번째 상담을 수행 했을 때 값 (dp[next] + p[i])를 비교해 큰값으로 업데이트한다.

import sys


n = int(sys.stdin.readline().strip())
t = [0] * (n + 1) #i번쨰 날 수행하는 상담 기간
p = [0] * (n + 1) #i번째 상담을 수행 했을 때 받는 페이
dp = [0] * (n + 2) # 메모이제이션 : i번째 날 상담을 수행 했을 때 받을 수 있는 최대 페이

for i in range(1, n + 1):
    t[i], p[i] = map(int, sys.stdin.readline().strip().split(" ")) #입력

for i in range(n, 0, -1): #뒤쪽에서부터 업데이트
    next = i + t[i] # i번째 상담을 수행했을 때 다음 상담을 수행 할 수 있는 날짜

    dp[i] = dp[i + 1] if next > n + 1 else max(dp[i + 1], dp[next] + p[i])
	# 다음 수행 날짜가 n+1보다 크면 전 날(i+1) 값으로 업데이트
    # 아니라면 전날 값과 i번째 날 상담을 수행했을 때 값을 비교해 업데이트
    
print(dp[1])

2. DFS(깊이 우선 탐색)

- i 번째 상담을 할 때와 하지 않을 때로 나누어 수행한다.

- 현재 날짜(day)에 상담기간(T[day])을 더해준 날짜가 퇴사일(N)보다 작다면 day의 상담이 종료하는 날짜(day + T[day])와 현재 수익에 상담 페이(profit+P[day])를 더해준 값에 대해 재귀적으로 dfs를 수행한다.

- 위 단계와 별개로 현재 날짜에 있는 상담을 안할 수도 있기 때문에 현재날짜에 1을 더한값(day+1) 과 현재 profit에 대해서도 재귀적으로dfs를 수행해준다.

- 재귀적으로 수행하다가 day가 퇴사날이 되면 현재까지 업데이트된 값 중 최대값(ans)과 현재 profit을 비교해 더 큰값으로 업데이트하고 재귀를 종료한다(return)

 

N=int(input())
S=[0 for i in range(N)]
P=[0 for i in range(N)]
for i in range(0,N):
    S[i], P[i] = map(int, input().split())

ans =0

def solve(day, profit):
    if day == N: #퇴사 날이 되면 수익을 업데이트 해준다.
        global ans
        ans = max(profit, ans)
        return

    if day + S[day] <= N: #day의 상담을 먹는 경우
        solve(day + S[day], profit+P[day]) #

    solve(day + 1, profit) #안먹는 경우

solve(0, 0)
print(ans)