- Problem Link : https://www.acmicpc.net/problem/문제번호
문제
- N이 주어지고 N+1일째 되는 날 퇴사한다.
- 스케줄표에 있는 상담을 받으면 해당하는 T일 동안 상담을 진행하고 P 만큼 금액을 얻는다.
- N+1일에 퇴사할 수 있도록 상담을 받아 최대 금액을 구하시오
- 이 때 퇴사할 수 있다는 뜻은 상담을 받는 날짜가 N일을 넘어가면 안됨
입력
- 첫째 줄, N이 주어진다.
- 둘째 줄, N개의 줄에 T와 P가 주어진다.
- 1일부터 N일까지 순서대로 주어진다.
출력
- 첫째 줄, 최대 이익을 출력한다.
풀이에 앞서
전형적인 다이나믹 프로그래밍(Dynamic Programming) 문제이다. 다이나믹 프로그래밍이 뭔지에 대해 이해해보자.
동적 계획법(Dynamic Programming, DP)이란?
복잡한 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말이다. 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
동적 계획법이란 말 때문에 어떤 부분에서 동적으로 프로그래밍이 이루어지는 찾아볼 필요가 없다.코딩 테스트에 자주 등장하는 단골 문제 유형이기 때문에 개념을 알아두면 좋다. 경우의 수가 엄청나게 큰 값의 문제들이 대부분 DP를 이용해서 풀어야하는 경우가 많다.
입력의 제한 사항이 몇 만 단위이거나 출력의 제한으로 경우의 수를 나눈 나머지를 출력하라고 하는 DP를 항상 염두해두자.
분할 정복(Divide and Conquer)과의 차이는?
거의 비슷하지만 결정적인 차이로는 작은 문제의 중복이 일어나는지 안일어나는지이다. 분할 정복은 큰 문제를 해결하기 어려워 작은 문제로 나누어 푸는 것이므로 작은 문제의 반복이 일어나지는 않는다. 그에 반해 동적 계획법은 작은 부분 문제들이 반복되는 것을 이용해 풀어나가는 방법이다.
동적 계획법 방법
모든 작은 문제들은 한 번만 풀어야한다. 즉, 다른 큰 문제가 들어왔을때 기존에 풀었었던 만약 같은 작은문제가 필요하다면 해당 작은 문제를 가져와서 사용할 수 있어야 한다. 따라서 내가 풀어낸 작은 문제의 결과값을 저장해놓아야 다음에 큰 문제를 풀어나갈때 사용할 수 있다.
동적 계획법 조건
동적 계획법을 적용하려면 두 가지 속성을 만족 시켜야 한다.
-
부분 반복 문제 (Overlapping Subproblem)
- 모든 문제를 부분 묹베로 쪼갤 수 있고, 재귀 함수를 통해 해결할 수 있다. -
최적 부분 구조 (Optimal Substructure)
- 작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 한다.
동적 계획법 접근 방법
동적 계획법으로 문제를 해결 할때는 크게 2가지 접근 방법을 들 수 있다.
- Top-Down 방법
- 위에서 아래로 접근하는 방법, 큰 문제에서 부분 문제로 쪼개가면 재귀 호출을 이용하여 푸는 방법
- Bottom-Up 방법
- 아래에서 위로 접근하는 방법, 부분 문제에서부터 문제를 풀어가며 점차 큰 문제를 풀어가는 방법
풀이
따라서 동적 계획법을 이용해 i번째 구할 수 있는 최대 금액을 저장해둔 후 그 다음 날짜를 구할 때 해당 날짜의 최대 금액을 이용해서 문제를 푸는 방식으로 코드를 작성했다.
Bottom-Up
부분 문제를 기록할 dp 리스트를 생성한 후 dp에는 i번째 일까지 얻을 수 있는 최대 수익이 담기게 된다. 따라서 우리가 원하는 것은 dp[N]의 값, dp[-1]값을 구하면 된다.
과정은 다음과 같다.
- i는 0일부터 N-1번째일까지 반복한다.
- j는 i + schedule[i][0], 즉 i번째날 상담을 받고 끝난 날부터 마지막 날까지 반복
- j번째 날의 현재 금액이 i번째 날의 상담을 받고 난 후에 증가되는 금액보다 작다면 i번째 상담을 받아야 최대 금액이므로 dp[j]의 최대금액을 상담 이후 금액으로 변경한다.
이렇게 작성해야만 중간 중간 상담을 받지 않은 경우도 포함시켜 확인할 수 있다.
for i in range(n):
for j in range(i + schedule[i][0], n + 1):
if dp[j] < dp[i] + schedule[i][1]:
dp[j] = dp[i] + schedule[i][1]
print(dp[-1])
Top-Down
위에서부터 반대로 내려올 수 있다.
for i in range(n - 1, -1, -1):
if i + schedule[i][0] > n:
dp[i] = dp[i + 1]
else:
dp[i] = max(dp[i + 1], schedule[i][1] + dp[i + schedule[i][0]])
print(dp[0])위 과정을 반대로 N일부터 올라가는 건데
1. i는 N일부터 0일까지 반복한다.
2. 만약 i + schedule[i][0]이 N일을 넘긴다면 그 상담은 받으면 않되므로 다음날 금액을 그대로 전날로 옮긴다.
3. 상담을 받지 않고 그냥 금액이 그대로 전날로 넘어가는 것과, i번째날에 상담을 받고 금액을 받은 경우 dp[i + schedule[i][0]]) 중 더 큰 것을 선택한다.
- dp[i + schedule[i][0]])로 작성하는 이유? N번째 일은 0으로 앞날짜로 갈수록 금액이 커지는 구조이다. 따라서 i일에 상담을 받은 후의 날짜(dp[i + schedule[i][0]])의 금액과 상담으로 인해 받는 날짜의 금액을 더해야 총 벌 수 있는 금액을 구하는 것이다.
코드
Bottom-Up
# Bottom - Up
import sys
input = sys.stdin.readline
n = int(input())
schedule = [list(map(int, input().split())) for _ in range(n)]
dp = [0 for i in range(n + 1)]
for i in range(n):
for j in range(i + schedule[i][0], n + 1):
if dp[j] < dp[i] + schedule[i][1]:
dp[j] = dp[i] + schedule[i][1]
print(dp[-1])
Top-Down
# Bottom - Up
import sys
n = int(input())
schedule = [list(map(int, sys.stdin.readlinet().split())) for _ in range(n)]
dp = [0 for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
if i + schedule[i][0] > n:
dp[i] = dp[i + 1]
else:
dp[i] = max(dp[i + 1], schedule[i][1] + dp[i + schedule[i][0]])
print(dp[0])
