Notice
Recent Posts
Recent Comments
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
Tags
more
Archives
Today
Total
관리 메뉴

No Limitation

[DP] 퇴사2 - 백준 본문

프로그래밍

[DP] 퇴사2 - 백준

yesungcho 2022. 2. 4. 13:48

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

 

15486번: 퇴사 2

첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)

www.acmicpc.net

 

참고 포스팅

https://j2wooooo.tistory.com/42

 

결국 이 문제 역시 점화식으로 푸는 문제였다.

각 일별 최적의 수익을 정리하기 위해서는 다음 논리로 갈 수 있다.

 

예를 들어

x일 날의 최적의 수익은 다음 중 하나이다.

  • x일 상담 끝나는 날짜가 퇴사 일을 넘기는 경우 → x일의 최적의 수익은 x+1일의 최적의 수익과 동일하다 ( dp[x] = dp[x+1] )
  • x일 상담 끝나는 날짜가 퇴사 일을 넘기지 않는 경우
    • x일 날 상담을 진행 안 하는 경우 → x일의 최적의 수익은 x+1일의 최적의 수익과 동일
    • ( dp[x] = dp[x+1] )
    • x일 날 상담을 진행할 수 있는 경우 → x일의 최적의 수익은 해당 날짜의 상담을 진행하고 마감 날짜의 최적 수익이 더해지는 경우와 같음
    • ( dp[x] = value[x] + dp[x+times[x]] )
    • 이 중 더 이익이 큰 경우가 x일의 최적의 수익이 된다
    • dp[x] = max(dp[x+1], value[x]+dp[x+times[x]])

이러한 논리로 점화식을 세워 문제를 푸는 것이 논리의 흐름

 

코드 구현은 다음과 같다. 

N = int(input())
times=[0]*(N+2); values = [0]*(N+2); 
for i in range(1,N+1) :
    time, value = [int(x) for x in input().split()]
    times[i] = time
    values[i] = value

dp = [0]*(N+2)

for i in range(N, 0, -1) :
    if i+times[i] > N+1 :
        dp[i] = dp[i+1]
    else : 
        v1 = values[i] + dp[i+times[i]]
        v2 = dp[i+1]
        dp[i] = max(v1, v2)

print(max(dp))

 

'프로그래밍' 카테고리의 다른 글

[DP] BOJ 거리 - 백준  (0) 2022.02.04
[DP] 1, 2, 3 더하기 4 - 백준  (0) 2022.02.04
[구현] 삼각 달팽이 - 프로그래머스  (0) 2022.02.04
[Greedy] 동전0 - 백준  (0) 2022.02.03
[DP] 평범한 배낭 - 백준  (0) 2022.02.03