백준 1463 - 1로 만들기

문제 설명

 

 

=> DP 문제이다. 

=> 내가 구해야 하는 것을 우선적으로 문자로 써본다. 

 

 

 

 

 

 

내가 구하고자 하는 것 : N 을 1로 만드는데 필요한 최소 연산 횟수 

 

가능한 경우의 수 : 

 

1.  i 가 3으로 나누어 떨어질 때

- arr[ i/3 ] + 1

 

2.  i 가 2로 나누어 떨어질 때

- arr[ i/2 ] + 1

 

3.  i 에서 1을 뺄 때

- arr[ i - 1 ] + 1

 

 

 

 

 

 

=> 위의 경우 세 가지가 있는 것을 알 수 있다. 

=> DP에는 Top-down 방식과 Bottom-up 방식이 있다.

=> 본인은 Bottom-up 방식을 선호한다. (Top-down은 재귀를 쓰는데, 재귀를 쓰다 보면 헷갈린다....)

 

*** 둘 중 어느것이 좋다는 것은 없다. 본인이 원하는 방식으로 사용하면 된다. 

 

 

 

 

#include <iostream>
#include <algorithm>


using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int N;
    cin >> N;
   
    int arr[1000001] = {0, };
    arr[1]=0;
    for( int i=2; i<= N; i++)
    {
        arr[i] = arr[i-1] +1;
        
        if( i%2 == 0 && arr[i] > arr[i/2] + 1)
        {
            arr[i] = arr[i/2] +1;
        }
        if( i%3 ==0 && arr[i] > arr[i/3] + 1)
        {
            arr[i] = arr[i/3] + 1;
        }
    }
    
    cout << arr[N]<<'\n';
    return 0;
}

 

 

 

 

 

 

실행 화면

 

 

실행 화면 2