1. 문제
https://www.acmicpc.net/problem/15486
2. 문제 이해
상담원에게 상담을 할 수 있는 기간, 그리고 그 기간동안 매일 하나씩 상담이 주어집니다.
각 상담은 완료까지 며칠이 걸리는지가 주어지고, 완료했을 때 가치가 주어집니다.
상담원은 상담을 선택할 수도 있고 안 할 수도 있습니다.
대신 상담이 진행 중이라면 새로운 상담을 선택할 수 없습니다.
이 때 상담원이 얻을 수 있는 최대 가치를 구하는 문제입니다.
각각 n개의 칸에서 시작하는 적당한 길이(T)의 막대가 있고, 막대에 값(P)이 정해져 있는 상황으로 바꾸어 생각할 수 있습니다.
겹치지 않게, 그리고 n을 넘지 않게 막대를 적당히 골라, 값의 합을 가장 크게 하는 문제로 바꾸어 이해할 수 있습니다.
3. 해결 방법
막대를 순서대로 하나씩 살펴보며 이전까지의 최대값과 다음 막대의 값을 활용하여 조건을 만족하는 값을 구할 수 있는 DP문제입니다.
그러나 막대를 살펴볼 때 두 가지 방법이 있습니다.
먼저 오름차순으로 살펴보는 방법입니다.
\(DP[i]\)는 0일차부터 i 일차까지 얻을 수 있는 최대값이고,
점화식은 \( DP[i + T_{i}] = max( \; DP[i + T_{i}], \; DP[i] + P_{i} \; ) \) 입니다.
이 과정을 거쳐서 문제를 풀어보니 DP[7]이 0이 되는 문제를 가지고 있습니다.
그리고 이 방법은 아래처럼 또 다른 문제도 생깁니다.
이렇게 되어서 답이 25인 것 같지만, DP[3] 에는 30으로 25보다 더 큰 값이 있고,
심지어 정답은 첫 번째 10과 세 번째 25를 선택한 35입니다.
이와 같은 문제가 발생하는 이유는, 각 과정의 결과가 아래와 같이 그 이후에 계속해서 영향을 주어야 하기 때문입니다.
이와 같이 수정할 경우 DP테이블의 제일 마지막에서 정답을 바로 확인할 수 있습니다.
하지만 막대를 살펴볼 때마다 뒤쪽의 모든 DP테이블의 값을 수정해야하는 비효율적인 과정이 포함됩니다.
이를 해결하기 위해 아래와 같이 DP[i]를 살펴볼 때 DP[i]의 값을 DP[i-1]과 비교해서 더 큰 값으로 바꾸어 주는 과정으로 바꾸면 됩니다.
다음으로 내림차순으로 막대를 살펴보겠습니다.
\( DP[i] \) 는 i일차부터 마지막날까지 얻을 수 있는 최대값이고,
점화식은 \( DP[i] = max( \; DP[i+1], \; DP[i+T-{i}] + P_{i} \; ) \) 입니다.
오름차순으로 할 때보다 더 간단하게 구현이 가능합니다.
오름차순으로 해결하려고 할 때 문제가 발생했던 상황도 살펴봅시다.
마찬가지로 더 구현하기 쉽고 효율적인 과정으로 진행이 됩니다.
4. DP를 역순으로 풀면 더 좋은 조건
앞서 본 것과 같이 이번 문제는 뒤에서 앞으로 푸는 방법이 더 좋습니다.
그렇다면 언제 역순으로 푸는 것이 더 좋을까요?
가. 미래의 정보가 현재 상태를 결정할 때
이번 문제에서 역순으로 해결할 경우 DP[i]를 구하기 위해 바로 다음 값인 DP[i+1]이 사용됩니다.
이처럼 i 번째 값을 구하기 위해 i+1 번째 값이 사용되는 경우에 역순으로 풀면 좋습니다.
나. 종료 조건(마지막 상태)이 명확하고 거기서부터 거꾸로 접근할 수 있을 때
이번 문제에서 DP[i]를 i 일차부터 마지막날(N)까지 얻을 수 있는 가치의 최대값이라고 할 때,
DP[N]은 무조건 0으로 명확합니다.
그리고 거기서부터 거꾸로 접근하는 것이 가능하고, 최종적으로 DP[0]은 전체 기간 동안 얻을 수 있는 최대값이 됩니다.
다. (0-1 배낭 문제처럼) 중복 선택이 불가능할 때
배낭 문제를 순방향으로 해결하면 한 아이템을 여러번 사용하는 중복 사용 문제가 발생할 수 있습니다.
예를 들어 배낭의 용량이 5이고, 물건의 무게가 2, 가치가 1인 경우 순방향과 역방향을 비교하면 다음과 같습니다.
5. 점화식으로 판단하는 방법
가. 핵심 관점
점화식에서
DP[i] = f(DP[이전 상태들])
이면 → 순방향
DP[i] = f(DP[미래 상태들])
이면 → 역방향
나. 순방향이 자연스러운 경우
점화식에 이전 상태가 들어가는 경우
DP[i] = max(DP[i - 1], DP[i - 2] + P[i])
- 예시: 계단 오르기, 동전 만들기, LIS(최장 증가 부분 수열)
- 현재 상태가 이전 상태의 결과에 의존
- 앞으로 나아가며 채우는 것이 직관적이고 깔끔함.
다. 역방향이 자연스러운 경우
점화식에 미래 상태가 들어가는 경우
DP[i] = max(DP[i + 1], P[i] + DP[i + Ti])
- 예시: 퇴사 문제, 일부 배낭 문제(0-1 Knapsack 역방향), 백트래킹 최적화 DP
- 현재 상태에서 미래 선택 여부를 고민해야 하므로
- 뒤에서부터 거꾸로 채워야 미래 정보가 이미 계산되어 있음.
