동적 계획법 모델화하기
서론
세상에는 수없이 많은 알고리즘 문제가 있습니다. 그러나 새로운 문제를 볼 때마다 항상 지금껏 보지 못한 새로운 기법을 사용해야 하는 것은 아닙니다. 문제의 특성을 파악하고, 조건들을 이용하여 자신이 아는 문제로 변환한 뒤, 이전에 다른 문제를 풀 때 사용했던 기법을 비슷하게 적용하여 풀 수 있기도 합니다. 이처럼 많은 문제는 몇 가지 정해진 전형적인 형태로 모델화 되는 경우가 많습니다.
반면에 큰 알고리즘 분류 중에 많은 사람들이 처음 접할 때 큰 벽을 느끼는 분야가 있습니다. 바로 동적 계획법(dynamic programming) 입니다. 동적 계획법을 입문하기 어렵다고 느껴지는 이유는 주로 이 모델화에 있습니다. 이 글에서는 동적 계획법 문제들을 어떻게 접근하는 것이 좋을지 이 모델화를 중심으로 살펴보고, 몇 가지 예시 문제를 통해 적용해 보도록 하겠습니다.
동적 계획법을 그래프로 모델화하기
동적 계획법은 대부분 그래프, 그 중에서도 사이클이 없는 유향 그래프(DAG) 로 모델화됩니다. 사실 문제로부터 이러한 그래프를 만들어내는 데에만 성공한다면 동적 계획법 문제는 다 푼 것이나 같다고 봐도 될 정도로 이 과정이 매우 중요하면서도 난이도가 높습니다.1
구성 요소
동적 계획법을 모델화한 그래프를 이루는 요소는 다음과 같습니다.
- 정점: 문제에서의 특정 상황을 유일하게 결정지을 수 있는 변수들로 이루어진 상태
- 간선: 상태간의 전이를 나타내는 점화식
각 정점은 자신의 상태에 대한 답을 갖습니다. 각 상태에서의 답을 나타내는 변수(배열)는 흔히 $dp$라고 이름짓고, 상태를 구성하는 변수는 순차적으로 배열의 각 차원을 담당합니다. 상태를 구성하는 두 변수가 $x$, $y$라면 $dp[x][y]$와 같은 형태로 특정 상태의 답을 나타내는 방식입니다.
점화식은 하나의 상태가 결정되기 위해 먼저 결정되어야 하는 다른 상태들과의 관계를 나타내는 식입니다. 예를 들어 $dp[x]=max(dp[x-1], dp[x-2])$라는 식은 점화식이 될 수 있고, 여기서 $dp[x]$가 결정되기 전에 먼저 결정되어야 하는 상태는 $dp[x-1]$과 $dp[x-2]$의 두 가지가 있음을 알 수 있습니다. 다른 상태와의 관계로 표현되지 않고 특정 상수를 답으로 가지게 되는 상태들도 존재하는데, 이들을 기저 상태라고 합니다.
동적 계획법에서 가장 어려운 것이 아마도 이 정점을 표현하기 위한 변수를 설정하는 일일 것입니다. 변수를 너무 많이 사용하면 상태의 수가 불필요하게 많아져 효율이 나빠질 수 있기 때문에 최소한의 상태와 최소한의 점화식을 사용하여 전체 상황을 유니크하게 표현할 수 있도록 만들어야 합니다. 이는 다양한 문제들을 통해 연습이 많이 필요한 부분입니다.
그래프의 조건
위에서 언급한 바와 같이 이렇게 구성된 그래프는 기본적으로 사이클이 없어야 합니다. 쉽게 말해서, 특정 상태에서 다른 상태로 도달한 후 다시 원래의 상태로 되돌아오는 방법이 존재하지 않아야 합니다.
이는 동적 계획법의 그래프 간선이 왜 ‘점화식’인지를 생각해 보면 명확합니다. 하나의 상태에 대한 답을 결정하기 위해 다른 상태의 답을 요구하는데, 그 상태의 답이 결정되기 위해 다시 자신의 답을 요구하는 일이 벌어진다면 두 상태의 답은 영원히 결정되지 못하고 서로가 먼저 결정해 주기를 미루기만 하게 될 것이기 때문입니다.
따라서 점화식을 만들 때에는 그래프가 항상 DAG 형태가 되는지를 생각해 보아야 합니다. 문제 자체에서 그러한 조건들끼리 사이클을 형성하지 않는다고 말해주면 편하지만, 그렇지 않은 경우에도 그래프가 DAG가 되는 확실한 경우들이 있습니다. 예시로는 다음과 같은 것들이 있습니다.
- 변수가 항상 감소 / 항상 증가하는 상태에서만 가져오는 경우: 예시로 $dp[i] = \max_{1 < j < i} dp[j] + C[i]$와 같은 것이 있으며, $j<i$인 $j$들로부터만 상태에 대한 답을 가져오므로 사이클이 형성되지 않습니다.
- 변수들의 합 / 차가 항상 감소 / 항상 증가하는 상태에서만 가져오는 경우: 예시로 $dp[s][e] = \max(dp[s+1][e], dp[s][e-1]) + C[s][e]$와 같이 범위를 변수로 가지는 경우에 자주 사용되며, $[s,e]$의 범위는 항상 $[s+1,e]$와 $[s,e-1]$의 범위보다 크기 때문에 상태간의 사이클이 형성되지 않습니다.
시간 복잡도
마지막으로 이 그래프를 탐색하는 데에 걸리는 시간 복잡도를 생각해 보아야 합니다. 동적 계획법을 구현할 때는 주로 탑-다운(top-down) 또는 바텀-업(bottom-up) 방식을 사용하는데, 어느 쪽이든 정점의 개수가 $V$이고 간선의 개수가 $E$일 때 $O(V+E)$의 시간이 걸리게 됩니다. 이 복잡도가 문제에 주어진 시간 제한에 들어맞는지를 계산해 보면 됩니다.
여기까지 문제가 없다면 동적 계획법 문제는 다 푼 것이나 다름 없습니다. 수식으로 적을 수 있다면 코드로 구현하는 것은 거의 옮겨적는 것에 불과하기 때문입니다. 정말로 그런지 예시 문제들을 보면서 확인해 보겠습니다.
예시 문제 1: 1로 만들기
가장 기초적인 동적 계획법 문제 중 하나인 1로 만들기입니다.2 이 문제를 먼저 그래프로 모델화 해보겠습니다.
먼저 이 문제에서의 상태는 다음과 같이 정의할 수 있습니다.
- $dp[x]$: $x$를 1로 만들기 위해 필요한 최소의 연산 횟수
상태를 결정하기 위해 $x$ 외에 다른 변수가 필요하지 않다는 것은 쉽게 알 수 있습니다. $x$만 고정되면 어떤 다른 요인도 존재하지 않기 때문에 답이 하나로 고정되어 나올 것이 분명하기 때문입니다. 또한 문제에서 구하고자하는 답은 $dp[N]$임도 바로 보입니다. 그러면 이제 각 상태를 결정하기 위해 어떤 점화식을 세울 수 있는지 생각해 봅시다.
… 그런데 사실 생각할 것도 없이, 문제에 그 점화식이 그대로 주어져 있습니다. 여기에 $x=1$이면 더 이상의 연산이 필요하지 않다는 조건을 추가하여 수식으로 표현해 봅시다.
- $dp[x] =
\begin{cases}
0, & x=1
\min \begin{cases} dp[x-1]
dp[\cfrac{x}{2}] + 1 & x \mod 2 = 0
dp[\cfrac{x}{3}] + 1 & x \mod 3 = 0 \end{cases} & x>1 \end{cases}$
다음은 이 그래프가 DAG를 만족하는지 생각해 보겠습니다. $x>1$인 모든 경우에, $dp[x]$를 결정하기 위해 먼저 결정되어야 하는 상태들인 $x-1$, $\cfrac{x}{2}$, $\cfrac{x}{3}$는 모두 $x$보다 항상 작기 때문에 방향이 고정되어 있고, 반대 방향으로 전이될 수 없으므로 사이클이 형성되지 않는다는 것을 확인할 수 있습니다.
마지막으로 이러한 그래프를 탐색하는 데에 소요되는 시간 복잡도를 생각해 보면, 상태의 개수가 $N$이고 각 상태를 결정하는 데에 필요한 점화식이 많아야 $3$개이므로 $O(N)$으로 쓸 수 있습니다. $N$이 최대 $10^6$이므로 이는 충분히 2초의 시간 제한 내에 돌아갑니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
int dp[1000005];
int main()
{
int n;
cin >> n;
dp[1] = 0;
for (int i = 2; i <= n; i++)
{
dp[i] = dp[i - 1] + 1;
if (i % 2 == 0)
dp[i] = min(dp[i], dp[i / 2] + 1);
if (i % 3 == 0)
dp[i] = min(dp[i], dp[i / 3] + 1);
}
cout << dp[n] << '\n';
}
바텀-업 방식으로 구현한 코드입니다. 바텀-업 구현은 점화식에서 선행되어야 하는 상태들부터 먼저 방문하여 답을 구해주는 방식으로, 이 문제에서는 항상 $dp[i]$에서 $i$가 작은 것부터 결정되어야 하기 때문에 $2$부터 $n$까지 순차적으로 방문하여 점화식을 그대로 적용한 것을 확인할 수 있습니다.
예시 문제 2: 가장 긴 증가하는 부분 수열
이 문제 또한 동적 계획법의 기초 문제로 많이 보게 되는 문제입니다. 같은 과정을 통해 그래프 모델화를 해보겠습니다. 수열의 원소를 $A[1]$부터 $A[N]$까지로 표현하면 다음과 같습니다.
- $dp[i]$: $A[i]$로 끝나는 가장 긴 증가하는 부분 수열의 길이
여기서도 역시 상태를 결정하는 데에 $i$ 이외의 다른 변수는 필요하지 않다는 것을 볼 수 있습니다. 문제의 정답은 반드시 어떤 수에서 끝나는 증가하는 부분 수열의 길이일 것이므로, $\max_{i=1..N}{dp[i]}$가 정답이 될 것입니다.
다음으로 점화식은 다음과 같이 세울 수 있습니다.
- $dp[i] = \max
\begin{cases}
1
\max_{1 \le j \lt i}{dp[j]+1} \quad where \ A[j] \lt A[i] \end{cases}$
즉, $A[i]$보다 더 작은 모든 $A[j]$ ($j<i$)들에 대해 가장 큰 $dp[j]$를 찾아 그 수열의 뒤에 $A[i]$를 덧붙이는 것이 $A[i]$에서 끝나는 가장 긴 증가하는 부분 수열이 됩니다. 이러한 $j$가 존재하지 않는다면 $A[i]$ 하나만을 단독으로 선택하는 것이 $A[i]$로 끝나는 가장 긴 증가하는 부분 수열이므로 $dp[i]=1$이 되어야 합니다.
이 점화식 역시 $dp[i]$를 결정하기 위해 항상 $i$보다 더 작은 $j$들로부터만 $dp[j]$ 값을 참조하므로 DAG가 성립하는 것을 볼 수 있습니다. 또한 상태의 개수가 $O(N)$이고, 각 상태를 결정하기 위해 참조해야 하는 이전 상태의 개수가 $O(N)$개이기 때문에 $O(N^2)$ 시간에 문제를 해결할 수 있음도 확인됩니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
int a[1005];
int dp[1005];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int ans = 0;
for (int i = 1; i <= n; i++)
{
dp[i] = 1;
for (int j = 1; j < i; j++)
if (a[j] < a[i])
dp[i] = max(dp[i], dp[j] + 1);
ans = max(ans, dp[i]);
}
cout << ans << '\n';
}
이 문제 역시 $i$가 증가하는 순서대로 $dp[i]$를 결정하면 됩니다. 1로 만들기 문제와의 눈에 띄는 차이점으로는 $dp[i]$를 결정하기 위해 확인해야 하는 상태가 $i$보다 작은 모든 $j$에 대해 이루어져야 하기 때문에 루프를 하나 더 돌고 있고, 따라서 시간 복잡도가 $O(n^2)$이 된다는 것이 있습니다.
예시 문제 3: 카드게임
이번에는 상태를 결정하는 변수가 두 개인 조금 더 어려운 예시를 하나 살펴봅시다. 이 문제는 지금까지와는 조금 다른 느낌의 상태가 필요합니다.
- $dp[a][b]$: 게임의 시작부터, 왼쪽 더미에서 $a$번째 카드, 오른쪽 더미에서 $b$번째 카드가 제일 위에 남아있게 되기까지 얻을 수 있는 점수의 최댓값
여기서는 $a$ 또는 $b$ 중 하나만을 가지고는 상태를 결정할 수 없음을 볼 수 있습니다. 왼쪽 더미에서 제일 위에 있는 카드가 같더라도 오른쪽 더미의 상태에 따라 지금까지 얻을 수 있는 점수가 달라질 수 있음이 확실합니다. 문제에서 구하고자 하는 답은 시작에서 도달할 수 있는 상태 중 한쪽 더미에 카드가 남아있지 않은 모든 상태들 중의 최댓값이 됩니다. 이게 어떤 의미인지 점화식을 세워보겠습니다. $x$, $y$는 각각 왼쪽, 오른쪽 더미의 카드를 위에서부터 나타낸 배열입니다.
- $dp[a][b] = \begin{cases}
0 & a = b = 1
\max \begin{cases} -inf
dp[a-1][b-1] & a > 1 \land b > 1
dp[a-1][b] & a > 1 \land b \le n
dp[a][b-1] + y[b-1] & a \le n \land b > 1 \land x[a] \gt y[b-1] \end{cases} & otherwise \end{cases}$
$a$와 $b$가 모두 $1$인 경우는 시작 케이스이기 때문에 답이 $0$인 것을 쉽게 알 수 있습니다. 그 외의 경우에는 문제에 적힌 것과 동일하지만, 추가적으로 ‘시작에서 도달할 수 없는 경우’를 고려해야 합니다. 이 문제의 경우 오른쪽 더미의 카드만 버리는 경우에 대한 제약 조건이 있기 때문에 일부 상태에는 도달이 불가능할 수 있습니다. 따라서 점화식을 통해 연결되는 이전 상태가 존재하지 않는 경우를 대비하여 $-inf$를 최솟값으로 두어야 합니다. 또한 한쪽 더미가 비게 되는 상태까지 봐야 하므로 $a$와 $b$는 $1$부터 $n+1$까지 각각 확인해봐야 합니다.
그런데 이 정의는 $dp[a][b]$를 확인하기 위해 $a$와 $b$에 대한 범위 검사를 많이 해야 하고, 또 $y[b-1]$을 참조해야 한다는 점이 일관성이 없어 보일뿐 아니라 시작에서 도달이 가능한지 여부 또한 판단해야 한다는 점이 아쉽습니다. 그래서 상태의 정의를 조금 달리 하는 것을 시도해볼 수 있습니다.
-
$dp[a][b]$: 왼쪽 더미에서 $a$번째 카드, 오른쪽 더미에서 $b$번째 카드가 제일 위에 남아있게 되었을 때부터 게임이 끝날 때까지 얻을 수 있는 점수의 최댓값
-
$dp[a][b] = \begin{cases} 0 & a = n+1 \lor b = n+1
\max \begin{cases} dp[a+1][b+1]
dp[a+1][b]
dp[a][b+1] + y[b] & x[a] > y[b] \end{cases} & otherwise \end{cases}$
두 정의는 사실 같은 그래프에서 간선의 방향만 바꾸어준 것에 불과하다는 것을 확인할 수 있습니다. 그렇지만 현재 상태에 오기 위한 이전 상태를 찾는 대신 현재 상태에서 갈 수 있는 다음 상태로부터 답을 받아오는 방식을 선택함으로써 위의 정의에서 불편했던 부분들이 모두 해소되었을 뿐 아니라, 문제의 정답이 항상 $dp[1][1]$에 존재하기 때문에 답을 찾는 것 또한 쉬워진 것을 볼 수 있습니다.
이 그래프가 DAG를 만족하는지 확인해 보면, $dp[a][b]$를 결정하기 위해 참조하는 다른 상태가 전자에서는 항상 $a$ 또는 $b$가 작아지는 방향으로, 후자에서는 $a$ 또는 $b$가 커지는 방향이기 때문에 역시 사이클 문제가 없음을 볼 수 있습니다. 또한 상태의 개수가 $O(N^2)$이고 각 상태에서 연결된 다른 상태의 개수가 $O(1)$이므로 시간 복잡도 역시 문제되지 않습니다.
구현 코드
우선 전자의 정의대로를 이전까지와 비슷한 방법(바텀-업)으로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
int x[2005], y[2005], dp[2005][2005];
const int inf = (int)1e9;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, a, b, i;
cin >> n;
for (i = 1; i <= n; i++)
cin >> x[i];
for (i = 1; i <= n; i++)
cin >> y[i];
int ans = 0;
for (a = 1; a <= n + 1; a++)
{
for (b = 1; b <= n + 1; b++)
{
if (a == 1 && b == 1)
{
dp[a][b] = 0;
continue;
}
dp[a][b] = -inf;
if (a > 1 && b > 1)
dp[a][b] = max(dp[a][b], dp[a - 1][b - 1]);
if (a > 1 && b <= n)
dp[a][b] = max(dp[a][b], dp[a - 1][b]);
if (a <= n && b > 1 && x[a] > y[b - 1])
dp[a][b] = max(dp[a][b], dp[a][b - 1] + y[b - 1]);
ans = max(ans, dp[a][b]);
}
}
cout << ans << '\n';
}
$a$와 $b$가 증가하는 순서대로 상태를 보면서 점화식을 그대로 적용하여 답을 구해주고 있지만, 조건문 등이 상당히 난잡한 것이 느껴집니다. 이번에는 후자의 정의대로 탑-다운으로 구현한 코드를 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int x[2005], y[2005], dp[2005][2005], n;
int solve(int a, int b)
{
if (a == n + 1 || b == n + 1)
return 0;
int &ret = dp[a][b];
if (ret != -1)
return ret;
ret = max(solve(a + 1, b + 1), solve(a + 1, b));
if (x[a] > y[b])
ret = max(ret, solve(a, b + 1) + y[b]);
return ret;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int i;
cin >> n;
for (i = 1; i <= n; i++)
cin >> x[i];
for (i = 1; i <= n; i++)
cin >> y[i];
memset(dp, -1, sizeof dp);
cout << solve(1, 1) << '\n';
}
solve 함수를 사용하여 $dp$ 값을 구하는 역할을 담당하도록 하고, 각 상태의 답을 구하기 위해 필요한 이전 상태들의 답은 solve 자신을 재귀호출하여 먼저 구하도록 하고 있습니다. 탑-다운 방식의 경우 같은 상태에 대한 답을 구하는 solve 호출이 여러 번 이루어질 수 있는데, 같은 상태에 대한 $dp$ 값은 하나로 고정되어야 하므로3 이미 이전에 답을 구한 경우 점화식을 다시 보지 않고 곧바로 답을 반환해주는 것을 볼 수 있습니다.
main 함수에서 solve(1, 1)을 호출하기 전 memset을 통해 배열 전체를 $-1$로 초기화하고 시작한 것을 볼 수 있는데4, 이는 각 상태가 아직 계산된 적이 없는 상태임을 의미합니다. 값이 $-1$인 것은 $-1$은 올바르게 구한 $dp$ 값으로 나올 수 없기 때문입니다. 만일 $-1$ 대신 $0$으로 초기화를 하게 되면 $dp$ 값이 이미 계산이 되었는데도 결과가 $0$인 것과 구분이 되지 않아 같은 상태에 대한 점화식을 여러 번 계산하여 ‘시간 초과’를 받게 되는 것을 볼 수 있습니다.
이 구현체는 함수의 호출 방향이 문제에 제시된 게임을 진행하는 것과 같은 조건과 같은 방향으로 이루어지고 있기 때문에 훨씬 직관적으로 보입니다. 문제 상황에 더 알맞은 상태와 점화식을 정의하도록 하는 것이 문제를 더 쉽게 보이게 해준 것입니다.
예시 문제 4: 팰린드롬 개수 구하기 (Large)
마지막으로 좀 어려운 문제를 하나 보겠습니다. 문자열을 나타내는 변수를 $S$ 대신 $X$로 쓰도록 하고, 모듈로를 제외하면 문제에서 구하고 싶은 것은 다음과 같습니다.
- $X$의 모든 부분 수열 중 팰린드롬인 부분수열의 개수
이 문제를 동적 계획법으로 풀기 위해, 이 최종 상태를 $S$의 부분 문자열에 대한 답으로 변환해 보겠습니다. $X$의 길이를 $n$이라고 하면,
- $X[1,n]$의 모든 부분 수열 중 팰린드롬인 부분수열의 개수
로 변환할 수 있습니다. 이제 $X$의 부분 문자열의 시작점과 끝점을 변수로 설정하면 다음과 같은 상태들을 만들 수 있습니다.
- $dp[s][e]$: $X[s,e]$의 모든 부분 수열 중 팰린드롬인 부분수열의 개수
현재까지의 상태의 개수는 $O(N^2)$이므로, 가능하면 상태마다 $O(N)$보다 작은 점화식을 연결하고 싶을 것입니다. 어떻게 할 수 있을까요? 이 글에서 중요하게 다루고자 하는 내용은 아니지만, 포함-배제의 원리를 사용하여 점화식을 세울 수 있습니다.
- $dp[s][e] =
\begin{cases}
0 & s > e
dp[s+1][e] + dp[s][e-1] - dp[s+1][e-1] + \begin{cases} 1 & X[s] = X[e]
0 & X[s] \ne X[e] \end{cases} & otherwise \end{cases}$
이 점화식을 해석하자면, 우선 $s > e$인 경우는 올바른 부분 문자열이 아니므로 답은 0입니다. 그 외의 경우에는 현재 부분 문자열에서 가장 왼쪽 문자를 제외한 나머지 부분 문자열에 대한 답 $dp[s+1][e]$와 가장 오른쪽 문자를 제외한 나머지 부분 문자열에 대한 답 $dp[s][e-1]$을 더해주는데, 이 답에는 두 부분 문자열에서 서로 겹치는 부분, 즉 $X[s+1,e-1]$에 대한 답 $dp[s+1][e-1]$이 중복되어 더해져 있기 때문에 이를 빼주는 것입니다. 마지막으로 $X[s]=X[e]$인 경우 $X[s]$와 $X[e]$를 이어붙인 부분 수열이 팰린드롬이므로 $1$을 더해주게 됩니다.
이 점화식은 각 상태에 대해 $O(1)$개의 점화식을 확인하면 되므로 시간 복잡도가 $O(N^2)$이고, $[s+1,e]$, $[s,e-1]$, $[s+1,e-1]$이 모두 $[s,e]$보다 작은 범위이므로 상태간의 사이클도 형성되지 않아 동적 계획법을 사용하는 데에 무리가 없습니다.
이와 같이 문자열이나 수열의 범위를 상태로 두고 범위끼리의 연관 관계를 이용한 동적 계획법 문제 역시 자주 출제되는 편입니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
const int mod = 10007;
string x;
int dp[1005][1005];
int f(int s, int e)
{
if (s > e)
return 0;
int &ret = dp[s][e];
if (ret != -1)
return ret;
ret = f(s + 1, e) + f(s, e - 1) - f(s + 1, e - 1) + mod;
if (x[s] == x[e])
ret += f(s + 1, e - 1) + 1;
return ret %= mod;
}
int main()
{
cin >> x;
memset(dp, -1, sizeof dp);
cout << f(0, (int)x.size() - 1) << '\n';
}
모듈로를 처리하는 부분이 추가된 것 외에는 위와 같은 전형적인 탑-다운 방식의 코드입니다. f(s + 1, e - 1)을 빼는 과정에서 음수가 될 수 있으므로 mod를 한 번 더해주는 것이 중요합니다.
결론
동적 계획법은 많은 프로그래밍 문제를 효율적으로 푸는 데에 핵심이 되는 기법이기 때문에 결국 입문을 해야 합니다. 널리 쓰이는 만큼 온갖 최적화 기법들이 존재하지만, 결국 모든 동적 계획법의 기본은 상태를 정하고 상태끼리의 점화식을 잘 세우는 것부터 시작이라는 것을 보았습니다. 그렇게 모델화한 그래프가 사이클을 형성하지는 않는지, 그래프를 탐색하는 시간 복잡도는 적절한지 등을 고려하는 것이 동적 계획법으로 접근하는 기초적인 수순입니다.