https://fuckingcomputer.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts%2F
TISTORY나를 표현하는 블로그를 만들어보세요.www.tistory.com
실버2인데 개어려움
기본적으로, 마지막날+1이어도 허용이 되므로, 마지막날+1을 만드는 아이디어가 중요하다.
다시풀라고해도 풀수있을지모르겠다.
2가지방법으로 풀 수 있다.
- 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]이 정답이다.
## dpn=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])