15486번 퇴사 2

15486번 (퇴사 2)

시간 제한	메모리 제한
2 초	512 MB

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.
오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.
각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.
N = 7인 경우에 다음과 같은 상담 일정표를 보자.

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	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

---

동적 계획법으로 최대 이익 구하기

문제 요약

N일 동안 상담 일정을 소화하여, 퇴사 전 얻을 수 있는 최대 이익을 구하는 문제입니다. 각 날짜 i에는 상담 소요 기간 Ti와 보수 Pi가 주어지며, 상담은 겹치지 않게 수행해야 합니다.

문제 분석

• 상담을 선택하면, Ti일 뒤에야 다음 상담을 시작할 수 있습니다.
• 퇴사일은 N+1일째이므로, 상담이 N일까지 모두 끝나야 합니다.
• 모든 가능한 상담 조합을 탐색하면 O(2^N)으로 불가능하므로, 효율적 알고리즘 필요.

DP 설계

DP 상태 정의
dp[i]를 i일부터 퇴사일까지 벌 수 있는 최대 이익이라 정의합니다.

전이식
i일에 상담을 선택하거나 건너뛰기 두 가지 경로가 있습니다.

• 건너뛰기: dp[i] = dp[i+1]
• 선택하기: 상담이 가능하면 dp[i] = dp[i + Ti] + Pi

따라서 최종 전이(점화식)는

$$
dp[i] = \max\bigl(dp[i+1],\; (i+T_i\le N+1)?\,dp[i+T_i]+P_i:\,0\bigr)
$$

flowchart TD
    Start[시작: i번째 날] --> Check{i + T_i ≤ N + 1?}

    Check -- 예 --> Take[상담 선택]
    Take --> TakeValue["이익: dp[i+T]+P"]

    Check -- 아니오 --> Skip[상담 안 함]
    Skip --> SkipValue["이익: 0"]

    TakeValue --> Compare["dp[i] = max(dp[i+1], 선택 이익)"]
    SkipValue --> Compare

    Compare --> End[다음 i로 이동]

코드 구현

원래의 퇴사 문제에서 사용한 코드는 이렇습니다.

def s():
    N,*TP=map(int,open(0).read().split())
    dp=[0]*(N+1)
    for i in range(N):
        for j in range(i+TP[(ii:=i<<1)],N+1):
            if dp[j]<(new:=dp[i]+TP[ii+1]):
                dp[j]=new
    print(dp[-1])
s()

설명

• TP는 [Ti, Pi, Ti, Pi, ...] 형식의 데이터입니다. i << 1은 2*i로, 각 날짜의 상담 기간과 보상 인덱스를 계산합니다.
• dp[i]: i일까지 가능한 최대 수익.
• i번째 날짜에서 상담을 시작한다고 할 때, i + T[i] 이후 날짜부터 이 상담의 결과가 반영됩니다.
• j는 상담이 끝난 다음 날부터 N일까지 모든 가능한 지점에 dp[j]를 업데이트합니다.
  • 이 말은 "상담을 시작하면, 그 끝 이후 날짜에 이 수익을 반영하자"는 의미입니다.

특징

• 정방향 탐색 (0 → N)
• 한 번의 상담 결과를 여러 날짜에 영향을 주는 방식 → 느릴 수 있음
• 직관적이나 불필요한 반복이 많음.

퇴사 2문제에서는 위 코드는 시간초과를 일으키며 아래와 같이 해결해야 통과됩니다.

def s():
    N, *TP = map(int, open(0).read().split())
    dp = [0] * (N + 2)  # N+1까지 필요 (i + T[i]가 N을 넘을 수도 있음)
    for i in range(N, 0, -1):
        ii = (i - 1) << 1
        t, p = TP[ii], TP[ii + 1]
        if i + t - 1 <= N:
            dp[i] = max(dp[i + 1], dp[i + t] + p)
        else:
            dp[i] = dp[i + 1]
    print(dp[1])
s()

설명

• i는 1부터 N일까지 날짜이고, ii = (i-1) * 2로 인덱스 접근.
• dp[i]: i일부터 가능한 최대 수익
• i + t - 1 <= N: 상담이 기간 안에 끝나는 경우
  • 두 가지 선택지 비교:
    • 상담을 하지 않을 경우: dp[i+1]
    • 상담을 할 경우: dp[i + t] + p
• 상담이 기간을 초과하면 그냥 dp[i+1]로 스킵

특징

• 역방향 탐색 (N → 1)
• 각 날짜마다 상담을 할지 말지를 결정하는 방식 → 효율적이고 명확
• 중복 계산 없음

두 코드의 핵심 차이점은 방향과 그로 인한 효과입니다. 이 두 관점에 집중해 비교해 보겠습니다.

---

🔁 방향 차이

항목 첫 번째 코드 두 번째 코드

탐색 방향	정방향 (앞 → 뒤)	역방향 (뒤 → 앞)
시작 시점	0일부터 N일까지	N일부터 1일까지
기준 관점	지금 선택하면 미래에 영향을 준다	미래 수익을 보고 지금 선택할지 말지 결정

---

🎯 효과 차이

🔸 첫 번째 코드 (정방향):

“지금 선택하면 이후에 반영”하는 구조

• 상담을 하면, 그 상담이 끝난 날부터 dp[j]에 그 이득을 반영함.
• j 범위가 넓어서 여러 dp[j]를 갱신 → 중복 계산 발생
• 이중 반복문 → 비효율적 (시간복잡도 ↑)

✅ 효과: 직관적이지만 비효율적. 불필요한 연산 많음.

---

🔸 두 번째 코드 (역방향):

“미래를 보고 지금 선택 여부를 판단”하는 구조

• 미래의 최대 수익 dp[i + T[i]]를 참고해서 지금 상담을 할지 결정
• 단일 반복문, 불필요한 연산 없음 → 효율적
• 미래에서부터 거꾸로 결정하니, 결정 순서가 간결하고 DP에 적합

✅ 효과: 효율적이고 빠름. 불필요한 연산 없이 깔끔하게 최대 수익 계산.

---

✅ 결론: 방향과 효과 요약

• 정방향 (1번 코드): 현재 선택이 미래를 바꾸는 방식 → 구현은 가능하지만 중복 계산으로 비효율적
• 역방향 (2번 코드): 미래 상태를 바탕으로 현재 선택을 결정하는 방식 → 효율적이고 실전 적합

👉 역방향 방식이 효과적이고 일반적으로 권장됩니다.

 

---

✅ 핵심 비교 포인트

항목	정방향 탐색	역방향 탐색
dp[i] 정렬됨	정답은 구할 수 있음	정답은 물론, 효율까지 확보
연산 방식	i + T[i] 이후 모든 j에 갱신 시도	i에서 단 한 번만 판단 후 갱신
중복 연산 가능성	높음 (같은 j를 여러 번 덮어씀)	없음 (미래 상태를 기반으로 1회만 계산)

---

📦 예제 입력

N = 10
TP = [
    1, 10,  # Day 1
    1, 10,  # Day 2
    1, 10,  # Day 3
    1, 10,  # Day 4
    1, 10,  # Day 5
    1, 10,  # Day 6
    1, 10,  # Day 7
    1, 10,  # Day 8
    1, 10,  # Day 9
    1, 10   # Day 10
]

💡 설명

• 하루마다 상담 가능 (기간 1), 보상 10
• 이 경우에는 무조건 매일 상담하는 것이 최적해
• dp[i] = 10 * (i - 1) 꼴로 단조 증가 → 정방향도 정답 보장됨

---

⏩ 정방향 탐색 연산 분석

for i in range(N):
    for j in range(i + T[i], N + 1):
        dp[j] = max(dp[j], dp[i] + P[i])

• i=0 → j=1~10 → dp[1]~dp[10] 10번 갱신
• i=1 → j=2~10 → 9번 갱신
• i=2 → j=3~10 → 8번 갱신
• ...
• i=9 → j=10 → 1번 갱신

🔢 총 연산 횟수 = 10 + 9 + 8 + ... + 1 = 55회

---

⏪ 역방향 탐색 연산 분석

for i in range(N, 0, -1):
    if i + T[i] - 1 <= N:
        dp[i] = max(dp[i+1], dp[i+T[i]] + P[i])
    else:
        dp[i] = dp[i+1]

• i = 10 → dp[10] = max(dp[11], dp[11] + 10)
• i = 9 → dp[9] = max(dp[10], dp[10] + 10)
• ...
• i = 1 → dp[1] = max(dp[2], dp[2] + 10)

🔢 총 연산 횟수 = 10회

---

✅ 결과 비교 요약

항목 정방향 탐색 역방향 탐색

반복문 횟수	55회	10회
정답 누락	❌ 없음 (정렬이 보장됨)	❌ 없음
중복 계산	많음 (dp[j] 반복 갱신)	없음 (1회만 판단)
코드 간결성	복잡	간단하고 명확

 

시간 복잡도

루프가 N회, 각 단계에서 O(1) 연산이므로 O(N)입니다. N ≤ 1,500,000이므로 충분히 빠릅니다.

마무리

동적 계획법의 기본 유형인 뒤에서부터 누적 계산을 활용하여 간단히 해결할 수 있습니다.
문제를 부분 문제로 나누고, 최적 부분 구조를 찾아 전이식을 세우는 연습이 중요합니다.

https://kimwooil.tistory.com/450

[450] 백준 15486번 - 퇴사 2(DP 역순)