1. 문제
https://www.acmicpc.net/problem/2240
2. 문제 이해
물체의 상태는 1 또는 2이고 처음 상태는 1입니다.
물체에게 정보가 1 또는 2가 임의로 최대 1000번 까지 순차적으로 주어지며, 물체의 상태와 같다면 값이 1 증가합니다.
물체는 정보가 주어질 때 자신의 상태를 바꿀 수 있으며 바꾸는 횟수는 최대 30번입니다.
이 때 얻을 수 있는 최대값을 구하는 문제입니다.
3. 해결 방법
가. 상태 변화 횟수와 현재 상태의 관계
상태는 두 개(1 또는 2)이고, 처음 상태는 1로 고정이 되어 있습니다.
상태를 홀수 번(1번, 3번, 5번, ...) 바꾼다면 상태는 2가 됩니다.
상태를 짝수 번(0번, 2번, 4번, ...) 바꾼다면 상태는 1이 됩니다.
다시 말해 상태 변화 횟수로 현재의 상태를 알 수 있고, 상태 변화 횟수를 관리한다면 현재의 상태를 따로 관리할 필요가 없습니다.
나. 현재 최적해는 결국 이전 상태의 최적해가 결정
t번째에 상태 변화를 w번 했을 경우의 최적해가 dp[t][w]라고 해봅시다.
(w가 홀수이면 현재 상태는 1, 짝수이면 현재 상태는 2일 것입니다.)
dp[t][w]는 dp[t-1][w] 또는 dp[t-1][w-1] 중 더 큰 수가 될 것입니다.
그리고 주어진 정보(1 또는 2)에 따라 1을 더하거나 더하지 않게 될 것입니다.
따라서 점화식은
dp[t][w] = max( dp[t-1][w], dp[t-1][w-1] ) + (1 또는 0)
입니다.
2, 1, 1, 2, 2, 1, 1 이 주어지고, 변화 횟수는 최대 2라고 하면 dp 테이블은 다음과 같은 순서로 채워집니다.
먼저 t가 0일 때(초기화)는 w에 상관없이 값은 모두 0입니다.
그 다음 윗줄(t-1)에서 같은 칸(w)과 왼쪽 칸(w-1) 중 큰 값을 선택하고 주어진 정보에 따라 1을 더해줍니다.
순차적으로 하면 다음과 같이 dp 테이블이 완성됩니다.
dp 테이블의 마지막 줄에서 최대값은 w가 2일 때 6으로 최대입니다.
다시 말하면 상태 변화를 2번 해서 최대값 6을 얻을 수 있습니다.
dp[t][w] 가 dp[t-1][w-1] 과 dp[t-1][w] 중 어떤 것을 선택했는지 역으로 살펴보면 언제 상태 변화를 했는지도 알 수 있습니다.
4. DP(동적 계획법) 문제의 재미
점화식을 이해하고, dp 테이블을 채우는 방법만 알면 이 문제는 매우 쉬워집니다.
나아가 동적 계획법으로 묶이는 수많은 문제들이, 결론적으로 점화식을 찾아내고 dp 테이블을 작성하는 과정만 잘 떠올릴 수 있다면 대부분 쉽게 풀어낼 수 있습니다.
그러나 정답을 찾아내는 이 방법을 떠올리기란 매우 어렵습니다.
바로 이런 특징이 동적 계획법을 매력적으로 만들어주는 것 같습니다.
제바스티안 슈틸러의 책 "알고리즘 행성 여행자들을 위한 안내서"에 보면 좋은 수수께끼의 조건이 나와있습니다.
풀어내기는 매우 어려우나, 힌트를 하나 얻으면 곧바로 정답을 알아차릴 수 있는 수수께끼가 좋은 수수께끼라고 합니다.
동적 계획법 문제가 바로 그런 좋은 수수께끼인 것 같습니다.
동적 계획법 문제를 풀다보면 며칠을 끙끙대며 고민해도 도저히 풀 수 없지만, 어느 순간 "맞아, 바로 그거였어!" 하며 쉽게 풀리는 경험을 하곤 합니다.
그럴 때마다 번쩍이는 희열을 느끼며 동적 계획법 문제의 재미에 빠져드는 것 같습니다.
