[백준 1463] 1로 만들기

0. 제목

• 백준 1463 1로 만들기
• BOJ 1463 1로 만들기
• C++ 1로 만들기

---

1. 문제

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

---

2. 풀이

• DP 방식을 이용하였다.
• Top-down방식과 Bottom-up방식 중에 Top-down방식을 사용하였다.
• Top-down방식을 이용할 땐 dp 배열을 10^6 보다 큰 수로 채워놓으면 된다.
• 먼저 초기값을 설정한 후, dp[i] = 1 + dp[i-1],  dp[i] = min(dp[i], 1 + dp[i/3]), dp[i] = min(dp[i], 1 + dp[i/2]) 와 같은 방법으로 연산횟수의 최솟값을 구한다.

---

3. 코드

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int dp[1000001];
    int X;
    cin >> X;
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;
    for(int i = 4; i <= X; i++){
        dp[i] = 1 + dp[i-1];    //아래에서 최솟값을 사용하기 위하여 먼저 처리
        if((i % 3) == 0)
            dp[i] = min(dp[i], 1 + dp[i/3]);    //min으로 최솟값 찾는 것이 point
        if((i % 2) == 0)
            dp[i] = min(dp[i], 1 + dp[i/2]);    //else if 가 아니고 if로 처리
    }
   
    cout << dp[X] << '\n';
    return 0;
}