[백준] 1463번. 1로 만들기 C++

www.acmicpc.net/problem/1463

1463번: 1로 만들기

>문제 설명

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

1. 첫번째 풀이 (완전 틀림)

 dp를 다시 오랜만에 풀려니 까먹어버렸다. 처음엔 아래 코드처럼 i=1부터 시작해서 지금 인덱스 i를 기준으로 dp[i*3], dp[i*2], dp[i+1]에 정보를 저장해줬는데,, 무슨 생각으로 이렇게 푼 건지 모르겠다..!! iteration 형태로 bottom-up으로 풀고 싶어서 반복문을 어찌저찌 써놓긴 했는데, 정작 하는 건 엉뚱한 짓.. dp 개념을 헷갈린 것 같다.. 지금 보는 애들 기준으로 전에 거쳐왔던 애들의 정보를 갖다 써야하는 것인데..! 그래서 다시 풀었다.

#define MAXN 1000001
#include <iostream>
#include <string.h>
using namespace std;

int n;
int dp[MAXN];

int main()
{
    cin>>n;
    
    int i=0;
    memset(dp, -1, sizeof(dp));
    
    while(true){
        
        //1부터 시작
        //dp[i*3] i 저장
        //dp[i*2] 값 없으면 i 저장
        //dp[i+1] 값 없으면 i 저장
        
        if(i*3 <= n) dp[i*3] = i;
        
        if(dp[i*2] == -1 && i*2 <= n) dp[i*2] = i;
        
        if(dp[i+1] == -1 && i <= n) dp[i+1] = i;
        
        if(dp[n] != -1) break;
        
        i++;
    }
    
    cout<<dp[n]<<"\n";

    return 0;
}

 

2. 맞은 풀이

#define MAXN 1000001
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

int n;
int dp[MAXN];

int main()
{
    cin>>n;
    
    memset(dp, MAXN, sizeof(dp));
    dp[1] = 0;
    
    for(int i=2; i<=n; i++){
        
        //1부터 시작
        //dp[i/3], dp[i/2], dp[i-1] 중에 최솟값 저장
        int div3 = MAXN;
        int div2 = MAXN;
        
        if(i%3 == 0) div3 = dp[i/3]+1;
        if(i%2 == 0) div2 = dp[i/2]+1;
        dp[i] = min(div3, div2);
        dp[i] = min(dp[i], dp[i-1]+1);

    }
    
    
    cout<<dp[n]<<"\n";

    return 0;
}

 

ㅎ dp 공부한지 얼마나 됐다고 벌써 까먹어서 실버3인데 헤매고 있다.. 그래도 고쳐 푸는데 얼마 안걸린걸 위안으로 삼고 더 공부하러 가자..