πŸ“š Study/Baekjoon

[Gold V] 15486 - 퇴사2

윰갱 2025. 4. 20. 12:31

문제

μƒλ‹΄μ›μœΌλ‘œ μΌν•˜κ³  μžˆλŠ” λ°±μ€€μ΄λŠ” 퇴사λ₯Ό ν•˜λ €κ³  ν•œλ‹€.

μ˜€λŠ˜λΆ€ν„° N+1일째 λ˜λŠ” λ‚  퇴사λ₯Ό ν•˜κΈ° μœ„ν•΄μ„œ, 남은 N일 λ™μ•ˆ μ΅œλŒ€ν•œ λ§Žμ€ 상담을 ν•˜λ €κ³  ν•œλ‹€.

λ°±μ€€μ΄λŠ” λΉ„μ„œμ—κ²Œ μ΅œλŒ€ν•œ λ§Žμ€ 상담을 작으라고 뢀탁을 ν–ˆκ³ , λΉ„μ„œλŠ” ν•˜λ£¨μ— ν•˜λ‚˜μ”© μ„œλ‘œ λ‹€λ₯Έ μ‚¬λžŒμ˜ 상담을 μž‘μ•„λ†“μ•˜λ‹€.

각각의 상담은 상담을 μ™„λ£Œν•˜λŠ”λ° κ±Έλ¦¬λŠ” κΈ°κ°„ Ti와 상담을 ν–ˆμ„ λ•Œ 받을 수 μžˆλŠ” κΈˆμ•‘ Pi둜 이루어져 μžˆλ‹€.

N = 7인 κ²½μš°μ— λ‹€μŒκ³Ό 같은 상담 μΌμ •ν‘œλ₯Ό 보자.

 1일2일3일4일5일6일7일TiPi
3 5 1 1 2 4 2
10 20 10 20 15 40 200

1일에 μž‘ν˜€μžˆλŠ” 상담은 총 3일이 걸리며, μƒλ‹΄ν–ˆμ„ λ•Œ 받을 수 μžˆλŠ” κΈˆμ•‘μ€ 10이닀. 5일에 μž‘ν˜€μžˆλŠ” 상담은 총 2일이 걸리며, 받을 수 μžˆλŠ” κΈˆμ•‘μ€ 15이닀.

상담을 ν•˜λŠ”λ° ν•„μš”ν•œ 기간은 1일보닀 클 수 있기 λ•Œλ¬Έμ—, λͺ¨λ“  상담을 ν•  μˆ˜λŠ” μ—†λ‹€. 예λ₯Ό λ“€μ–΄μ„œ 1일에 상담을 ν•˜κ²Œ 되면, 2일, 3일에 μžˆλŠ” 상담은 ν•  수 μ—†κ²Œ λœλ‹€. 2일에 μžˆλŠ” 상담을 ν•˜κ²Œ 되면, 3, 4, 5, 6일에 μž‘ν˜€μžˆλŠ” 상담은 ν•  수 μ—†λ‹€.

λ˜ν•œ, N+1μΌμ§Έμ—λŠ” νšŒμ‚¬μ— μ—†κΈ° λ•Œλ¬Έμ—, 6, 7일에 μžˆλŠ” 상담을 ν•  수 μ—†λ‹€.

퇴사 전에 ν•  수 μžˆλŠ” μƒλ‹΄μ˜ μ΅œλŒ€ 이읡은 1일, 4일, 5일에 μžˆλŠ” 상담을 ν•˜λŠ” 것이며, μ΄λ•Œμ˜ 이읡은 10+20+15=45이닀.

상담을 적절히 ν–ˆμ„ λ•Œ, 백쀀이가 얻을 수 μžˆλŠ” μ΅œλŒ€ μˆ˜μ΅μ„ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

μž…λ ₯

첫째 쀄에 N (1 ≀ N ≀ 1,500,000)이 μ£Όμ–΄μ§„λ‹€.

λ‘˜μ§Έ 쀄뢀터 N개의 쀄에 Ti와 Piκ°€ 곡백으둜 κ΅¬λΆ„λ˜μ–΄μ„œ μ£Όμ–΄μ§€λ©°, 1일뢀터 NμΌκΉŒμ§€ μˆœμ„œλŒ€λ‘œ μ£Όμ–΄μ§„λ‹€. (1 ≀ Ti β‰€ 50, 1 ≀ Pi β‰€ 1,000)

좜λ ₯

첫째 쀄에 백쀀이가 얻을 수 μžˆλŠ” μ΅œλŒ€ 이읡을 좜λ ₯ν•œλ‹€.

예제 μž…λ ₯ 1 λ³΅μ‚¬

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

예제 좜λ ₯ 1 λ³΅μ‚¬

45

예제 μž…λ ₯ 2 λ³΅μ‚¬

10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

예제 좜λ ₯ 2 λ³΅μ‚¬

55

예제 μž…λ ₯ 3 λ³΅μ‚¬

10
5 10
5 9
5 8
5 7
5 6
5 10
5 9
5 8
5 7
5 6

예제 좜λ ₯ 3 λ³΅μ‚¬

20

예제 μž…λ ₯ 4 λ³΅μ‚¬

10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50

예제 좜λ ₯ 4 λ³΅μ‚¬

90

# 풀이 방법

dpλŠ” N일에 얻을 수 μžˆλŠ” μ΅œλŒ€ 이읡을 μ˜λ―Έν•œλ‹€.

그리고 N일에 얻을 수 μžˆλŠ” 이읡은 N-1μΌκΉŒμ§€μ˜ κ²°κ³Όλ₯Ό 톡해 μ–»μ–΄μ§€κΈ° λ•Œλ¬Έμ—

for문을 돌 λ•Œ 미래λ₯Ό κ³ λ €ν•΄μ•Όν•œλ‹€. λ”°λΌμ„œ λ°°μ—΄μ˜ 크기도 N+1이 μ•„λ‹Œ N+2둜 μ„€μ •ν–ˆλ‹€.

 

μ†”μ§νžˆ μ²˜μŒμ— ν’€ λ•ŒλŠ” λ§‰λ§‰ν–ˆλ‹€.. dp에 μ΅μˆ™ν•΄μ Έμ•Ό ν•  λ“― γ… 


# μ½”λ“œ

# 2025-04-20 10:40-11:25 (풀이참고)
import sys
# sys.stdin = open("input.txt","r")
N = int(sys.stdin.readline())
table = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dp = [0] * (N + 2)  # dp[i] = i일에 얻을 수 μžˆλŠ” μ΅œλŒ€ 수읡

for i in range(1, N + 1):
    t, p = table[i - 1]

    # 였늘(i일)에 아무것도 ν•˜μ§€ μ•Šκ³  κ·Έλƒ₯ λ„˜μ–΄κ°€λŠ” κ²½μš°λ„ κ³ λ €
    dp[i + 1] = max(dp[i + 1], dp[i])

    # 였늘(i일)에 상담을 ν•œλ‹€λ©΄
    if i + t - 1 <= N:
        dp[i + t] = max(dp[i + t], dp[i] + p)

print(max(dp))  # N+1일에 끝났을 μˆ˜λ„ μžˆμ–΄μ„œ 전체 쀑 max