[백준알고리즘] 1463번 1로 만들기

https://www.acmicpc.net/problem/1463

1로 만들기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	57965	18815	12157	32.140%

문제

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

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

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

입력

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

출력

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

예제 입력 1 

2

예제 출력 1 

1

예제 입력 2 

10

예제 출력 2 

3

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

처음에는 뒤에서부터 채워나가는 것으로 만들었다.

앞부터 채울지 뒤부터 채울지 상관은 없지만

뒤에서부터 채울 때에는 매우큰 값으로 초기화를 해주어야 하기도 하고 코드를 직접 만들 때에는 쉬울 수 있으나

프로그램이 잘 짜여진 느낌이 아니라고나 할까 ㅠㅠ..?해서 앞에서부터 채워나가는게 좋은 것 같다.

앞에서 채우는 예제가 더 많이 나와있기도 하다!

사람들은 어떻게 이런식으로 코드 짤 생각을 바로 하는건지.. 신기하답..

최종적으로 앞에서부터 채워나간 코드!

#include<iostream>
using namespace std;
#define min(a,b) a< b ? a:b
 
int dp[1000001];
 
int main()
{
    int X = 0;
    cin >> X;
 
    for(int i = 2; i <= X; i++)
    {
        dp[i] = dp[i-1] + 1;
        // 3으로 나누어 떨어진다.
        if (i % 3 == 0)
        {
             dp[i] = min(dp[i/3]+1, dp[i]);
        }
        // 2로 나누어 떨어진다
        else if(i % 2 == 0)
        {
            dp[i] = min(dp[i/ 2]+1, dp[i]);
        }
    }
    cout << dp[X];
    return 0;
}