BOJ 12852 1로 만들기 2

 

문제 링크 : https://www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

 

주어진 연산을 이용해서 n 을 1 로 만드는데 필요한 비용(횟수) 외에도 경로도 출력한다는 것을 빼면 평범한 dp 문제.

n 을 무엇으로 줄이면 최적인가를 기록해두는 prv 배열을 도입하면 충분하다.

 

탑다운 방식과 바텀업 방식을 모두 소개하기 쉬운 문제라 기록해 둔다.

 

 

1. Top-Down

dp[n] 은 에 dp[n/3]+1 , dp[n/2]+1 이거나 dp[n-1]+1 중 작은 값이다.

( n 이 2, 3 의 배수가 아니면 앞의 항들은 사용하지 않는다.)

 

#include<bits/stdc++.h>

using namespace std;

const int Inf=1e9;
int dp[1000001], prv[1000001];

int recur(int n){
    if(n==1) return 0;
    int &ret=dp[n];
    if(ret) return ret;
    
    ret=Inf;
    if(n%3==0) {
        ret=recur(n/3)+1;
        prv[n]=n/3;
    }
    
    if(n%2==0) {
        int t=recur(n/2)+1;
        if(ret>t){
            ret=t;
            prv[n]=n/2;
        }
    }
    
    int t=recur(n-1)+1;
    if(ret>t){
        ret=t;
        prv[n]=n-1;
    }
    return ret;
}

int main(){
    int n; scanf("%d",&n);
    printf("%d\n", recur(n));
    for(int i=n;i!=0;i=prv[i])
        printf("%d ",i);
    printf("\n");
}

 

2. Bottom-Up 1

바텀업도 두 가지 방식으로 나누어보자.

탑다운에서 설명한 것과 같이  

i  를 줄여나갈 때 더 작은 수 i-1, i/2, i/3 중 무엇을 선택하는 것은 좋은가?

 

를 그대로 반영한 코드는 다음과 같다.

이 코드는 무늬는 바텀업이지만 i 에서 작은 수를 고려한다.

 

#include<bits/stdc++.h>

using namespace std;

const int Inf=1e9;
int dp[1000001], prv[1000001];

int main(){
    int n; scanf("%d",&n);
    for(int i=3;i<=n;i++) dp[i]=Inf;
    
    dp[1]=0, dp[2]=1, prv[2]=1;
    for(int i=3;i<=n;i++){
        if(dp[i]>dp[i-1]+1){
            dp[i]=dp[i-1]+1;
            prv[i]=i-1;
        }
        
        if(i%2==0 && dp[i]>dp[i/2]+1){
            dp[i]=dp[i/2]+1;
            prv[i]=i/2;
        }
        
        if(i%3==0 && dp[i]>dp[i/3]+1){
            dp[i]=dp[i/3]+1;
            prv[i]=i/3;
        }
    }
    
    printf("%d\n", dp[n]);
    for(int i=n;i!=0;i=prv[i])
        printf("%d ", i);
    printf("\n");
}

 

3. Bottom-Up 2

이번에는 반대로 i 가 더 큰 수를 만드는데 기여하는 바를 정리하자.

 

1~i 까지 최적의 방법을 알고 있다고 하자.

i 에서 1 을 만드는 최소 연산 횟수를 dp[i] 라 하면 3 가지 방식으로 기여할 수 있다.

dp[i+1] 을 결정하기 위해서는  dp[i]+1 을 고려해야 한다.

dp[2*i] , dp[3*i] 역시 마찬가지다.

 

이런 사고 방식을 적용한 것이 다음 코드이다.

i 에서 i 보다 큰 수를 들여다 본다는 점에서 바텀업이라 불리는데 이 코드가 더 어울려 보인다.

 

#include<bits/stdc++.h>

using namespace std;

const int Inf=1e9;
int dp[1000001], prv[1000001];

int main(){
    int n; scanf("%d",&n);
    for(int i=2;i<=n;i++) dp[i]=Inf;
    
    for(int i=1;i<n;i++){
        if(dp[i+1]>dp[i]+1){
            dp[i+1]=dp[i]+1;
            prv[i+1]=i;
        }
        
        if(2*i<=n && dp[2*i]>dp[i]+1) {
            dp[2*i]=dp[i]+1;
            prv[2*i]=i;
        }
        
        if(3*i<=n && dp[3*i]>dp[i]+1) {
            dp[3*i]=dp[i]+1;
            prv[3*i]=i;
        }
    }
    
    printf("%d\n", dp[n]);
    for(int i=n;i!=0;i=prv[i])
        printf("%d ", i);
    printf("\n");
}