동적계획법(경로 역추적)

• 경로 역추적

 

 

동적 계획법 문제에서는 단순히 문제의 해를 구하는 것 뿐만 아니라, 그 해를 구하기 위한 과정에서 선택해야 하는 요소들을 출력하는 문제도 존재한다. 이를 해결하기 위해선 동적계획법을 진행할 때, 메모이제이션을 통해 저장해놓은 값들을 활용하여 중간 단계에서 최종 단계까지 도달하기 위해 선택해야할 필수 요소들을 출력해야 한다. 예를 들어 BOJ 12852 1로 만들기 2 와 같은 문제에서는 입력받은 자연수 N을 1로 만들기 위해 수행해야하는 연산의 순서를 출력하는 문제이다. 예를 들어 N이 10이라면 최소 횟수인 4 뿐만 아니라 10 -> 9 -> 3 -> 1의 순서를 출력해야한다.

 

 

 

이 문제의 해를 구하는 과정을 동적계획법으로 구현하면 다음과 같다.

 

 

 

int memo[1000001];
 
int dp(int x)
{
    //종료 조건
    if(x==1) return 0;
    //이미 계산되었다면
    if(memo[x]!=-1) return memo[x];
    
    memo[x]=dp(x-1)+1;
    if(x%3==0) memo[x]=min(memo[x], dp(x/3)+1);
    if(x%2==0) memo[x]=min(memo[x], dp(x/2)+1);
    return memo[x];
}
 

 

 

 

---

 

 

 

 

동적 계획법을 진행하는 과정에서 초기의 수 N이 어떤 수 N'이 되었다고 하자. 수가 N'일 때 어떤 연산을 사용하는 것이 최적인지 어떻게 알 수 있을까?

 

 

 

우리는 N'에서 동적계획법을 시행했을 때, 나오는 값들을 통해 이를 확인해야 한다. $d_{i}$를 어떤 수 $i$를 1로 만들기 위해 시행하는 최소 연산 횟수라고 정의하자. 세 값 $d_{N'/3}, d_{N'/2}, d_{N'-1}$을 알고 있다고 할 때, 이 세 값에 대해서 다음이 성립한다.

 

 

 

• 만약 $d_{N'/3}$이 가장 작다면,   N'을 3으로 나누는 연산이 최적해를 구하기 위한 과정이다.
• 만약 $d_{N'/2}$이 가장 작다면,   N'을 2로 나누는 연산이 최적해를 구하기 위한 과정이다.
• 만약 $d_{N'-1}$이 가장 작다면,  N'에서 1을 빼는 연산이 최적해를 구하기 위한 과정이다.

 

 

 

위의 논리를 통해 10을 1로 만드는 과정을 구해보자.

 

 

 

N\연산의 종류	$d_{N/3}$	$d_{N/2}$	$d_{N-1}$	선택	다음 값
10	nan	3	2	$d_{N-1}$	9
9	1	nan	4	$d_{N/3}$	3
3	0	nan	1	$d_{N/3}$	1
1

 

 

 

 

10을 1로 만들려면

 

10%3!=0이므로 3으로 나누는 것은 불가능

2로는 나누어지므로 $d_{N/2}=d_{5}=3$이다.

$1$을 빼는게 가능하므로 $d_{N-1}=d_{9}=2$이다.

따라서 값이 가장 작은 1을 빼는 연산을 하고, 순서는 10 -> 9가 된다.

 

 

9를 1로 만들려면

 

9는 3으로 나누어떨어지므로 $d_{N/3}=d_{3}=1$이다.

9%2!=0

1을 빼는게 가능하므로 $d_{N-1}=d_{8}=4$이다.

따라서 값이 가장 작은 3으로 나누는 연산을 하고, 순서는 9 -> 3이 된다.

 

 

3을 1로 만들려면

 

3은 3으로 나누어지므로 $d_{N/3}=d_{1}=0$이다.

3%2!=0

1을 빼는게 가능하므로 $d_{N-1}=d_{2}=1$이다.

따라서 값이 가장 작은 3으로 나누는 연산을 하고, 순서는 3 -> 1이 된다.

 

 

 

 

 

그러므로10 -> 9 -> 3 -> 1 이라는 결과가 나온다. 위 논리를 구현한 코드는 다음과 같다.

 

 

 

#include <iostream>
#include <bits/stdc++.h>
 
using namespace std;
 
int memo[1000001];
 
int dp(int x)
{
    if(x==1) return 0;
    if(memo[x]!=-1) return memo[x];
    memo[x]=dp(x-1)+1;
    if(x%3==0) memo[x]=min(memo[x], dp(x/3)+1);
    if(x%2==0) memo[x]=min(memo[x], dp(x/2)+1);
    return memo[x];
}
 
 void tracking(int x) //경로 역추적
 {
     //출력
     printf("%d ", x);
     if(x==1) return; //1이면 종료
     int a, b, c;
     a=b=c=999999999;
     
 
     if(x%3==0) a=dp(x/3);
     if(x%2==0) b=dp(x/2);
     if(x>1) c=dp(x-1);
 
     if(a<=b && a<=c) tracking(x/3);
     else if(b<=a && b<=c) tracking(x/2);
     else if(c<=a && c<=b) tracking(x-1);
 
 }
 
 int main()
 {
     int n;
     scanf("%d", &n);
     memset(memo, -1, sizeof(memo));
     printf("%d\n", dp(n));
     tracking(n);
     return 0;
}

 void tracking(int x) //경로 역추적
 {
     //출력
     printf("%d ", x);
     //종료조건 : 1이면 종료
     if(x==1) return;
 
     //각 연산을 했을 때 얻을 수 있는 최솟값을 저장
     int a, b, c;
     a=b=c=999999999;
     
 
     if(x%3==0) a=dp(x/3);
     if(x%2==0) b=dp(x/2);
     if(x>1) c=dp(x-1);
 
     //가장 효율적인 연산을 결정
     //해당 연산을 수행하고 다음 값에 대해서도 
     if(a<=b && a<=c) tracking(x/3);
     else if(b<=a && b<=c) tracking(x/2);
     else if(c<=a && c<=b) tracking(x-1);
 
 }