[C++] BaekJoon 1463 1로 만들기

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

---

---

1. X가 3으로 나누어 떨어지면 3으로 나눈다.

2. X가 2로 나누어 떨어지면 2로 나눈다.

3. 1을 뺀다

 

이 3개의 연산을 최소한의 횟수로 1을 만드는 문제이다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> dp(N + 1);

    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;
    //dp[4] = dp[3] + 1 = 2
    //dp[5] = dp[4] + 1 = 3
    //dp[6] = dp[5] + 1 = 4 => 오류

    for (int i = 4; i <= N; i++) {
        dp[i] = dp[i - 1] + 1;

        if (i % 3 == 0) {
            dp[i] = min(dp[i], dp[i / 3] + 1);
        }
        if (i % 2 == 0) {
            dp[i] = min(dp[i], dp[i / 2] + 1);
        }
    }

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

    return 0;
}

 

설명

주어진 정수 N을 최소 몇번의 연산 뒤에 1로 만들 수 있는지를 구하는 문제이다. 

예를 들어보자.

 

N =2, "2로 나누어 떨어지면, 2로 나눈다" 1번 연산 후 1이 된다. 

따라서 최소 한번의 연산이 필요하게 된다. 

 

N = 3 "3으로 나누어 떨어지면, 3으로 나눈다." 1번 연산 후 1이 된다

따라서 최소 한번의 연산이 필요하게 된다.

 

이러한 연산의 규칙을 찾아보자.

 

< N = 4 >

4 -> 3 -> 1

4 -> 2 -> 1

 

< N = 5 >

5 -> 4 -> 2 -> 1

 

< N = 6 >

6 -> 3 -> 1

6 -> 2 -> 1

 

< N = 7 >

7 -> 6 -> 3 -> 1

7 -> 6 -> 2 -> 1

 

< N = 8 >

8 -> 4 -> 2 -> 1

8 -> 4 -> 3 -> 1

 

N = 4 ~ 8의 경우를 살펴보면 다음과 같은 규칙을 도출할 수 있다. 

 

N을 1로 만들기 위한 최소 횟수는 N -1을 1로 만들기 위한 최소 횟수 + 1

OR

2나 3으로 나누어지면, 나누고 남은 몫의 경우의 연산 + 1

 

이 두 경우를 비교하여 더 적은 값을 가진 선택해 출력하면 된다.