[백준] 퇴사 | 삼성

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

분류:: dp, dfs

 

1. 문제 이해 및 해결과정

- 뒤쪽부터 풀어 해결하는 DP - 뒤쪽부터 상담에 대해서 현재 상담 일자의 이익(p[i]) + 현재 상담을 마친 일자부터의 최대이익 dp[t[i]+i]] 을 계산하면됨 - dp[i] : i번째 날부터 마지막 날까지 낼 수 있는 최대 이익 - dp[i] = max(dp[i] + dp[t[i]+i]],maxv)  - maxv: 현재까지의 최대 상담금액

 

2. 풀이방법

  1. DP

#퇴사
#https://www.acmicpc.net/problem/14501
import sys
sys.stdin = open("input.txt","r")
n=int(input())
t=[] #각 상담을 완료하는 데 걸리는 기간
p=[] # 각 상담을 완료했을 때 받을 수 있는 금액
dp = [0]*(n+1) #dp테이블
maxv=0

for _ in range(n):
    a,b=map(int,input().split())
    t.append(a)
    p.append(b)

#뒤에서 부터 확인
for i in range(n-1,-1,-1):
    time=t[i]+i #현재날짜 + 상담할 경우 걸리는 기간 
    #상담이 기간 안에 끝나면
    #print(time,n)
    if time<=n:
        dp[i]=max(p[i]+dp[time],maxv)
        maxv=dp[i]
    #상담이 기간을 벗어나면
    else:
        dp[i]=maxv #현재까지의 최대 상담금액
    #print(dp)
print(maxv)

 2. DFS

#퇴사
#https://www.acmicpc.net/problem/14501
import sys
sys.stdin = open("input.txt","r")

n=int(input())
t=[] #걸리는 시간
p=[] #수익
res=-1e9
def dfs(day,sum):
    global res
    if day==n+1:
        if sum > res:
            res=sum
    else:
        if day+t[day]<=n+1: #상담이 가능한 경우
            dfs(day+t[day],sum+p[day])
        dfs(day+1,sum)

for i in range(n):
    a,b=map(int,input().split())
    t.append(a) 
    p.append(b)
t.insert(0,0) #인덱스번호를 날짜로 사용하기 위해
p.insert(0,0)
dfs(1,0)
print(res)

 

3. 오답원인

 

4. 알게된 점