백준 14051 퇴사

https://fuckingcomputer.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts%2F 

TISTORY

 

실버2인데 개어려움

기본적으로, 마지막날+1이어도 허용이 되므로, 마지막날+1을 만드는 아이디어가 중요하다.

다시풀라고해도 풀수있을지모르겠다.

 

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

1. dfs로, 0부터 시작해서 포함안하는 경우와,

만일 포함가능하다면, 포함하는경우까지 생각해서 dfs를진행하고,

마지막날+1까지 탐색했을때, 모든 경우의 수를 비교해 최대인 answer을 찾는다.

##dfs코드##

def dfs(index,value=0):
    global answer
    if index==n:
        if answer<value:
            answer=value
        return
        

    dfs(index+1,value) # 포함안하고 그냥 넘어가는 경우

    if index+arr[index][0]<=n:
        dfs(index+arr[index][0],value+arr[index][1]) #포함하면 그다음가능한날짜



##dfs 사용
n=int(input())
arr=[]
answer=0 #정답값
for _ in range(n):
    arr.append([* map(int,input().split())])

dfs(0)
print(answer)

2.Dp

dp를 처음부터 해결해나간다는 고정관념을 버려야한다.

앞서와 똑같은 이유로,마지막날을 해결하기 위해서 n+1의 dp 배열을 만든다.

dp[i]=뒤에서부터 i번째인덱스까지의 최댓값으로 정의

 

이후, n-1(arr의 마지막값) 부터 거꾸로 dp를 돌면서,

i+arr[i]가 n보다 큰 경우에는 실행불가이므로 dp[i]=dp[i+1]이 된다,(에러방지)

 

나머지 경우에는

dp[i]=max{포함하지않는경우, 포함하는경우}

즉

dp[i]=max(dp[i+1]   ,   dp[i+arr[i][0]]+arr[i][1] 이 된다.

dp[0]이 정답이다.

 

## dp

n=int(input())
arr=[]
answer=0 #정답값
for _ in range(n):
    arr.append([* map(int,input().split())])

dp=[0 for _ in range(n+1)] #마지막날에 1일이든다면, 해결하기위해서 n+1
#dp[i]=뒤에서부터 i까지갔을때 최댓값
for i in range(n-1,-1,-1):
    if i+arr[i][0]>n: #만일 n을 넘는다면, 에러방지
        dp[i]=dp[i+1] #더이상암것도못하므로, 전값으로대체
        continue

    else:dp[i]=max(dp[i+1],dp[i+arr[i][0]]+arr[i][1])
    #포함안하는 경우(전의값), 포함하는경우(상담이 끝나는날짜의 값+현재값의 가치)

print(dp[0])