[백준] 1463번 : 1로 만들기

문제

 

---

풀이

 

2와 3 모두로 나눌 수 있는 정수 i가 있을 때 이 정수 i를 1로 만드는 방법은 다음과 같다.

 

1. (정수 i/2를 1로 만드는 방법의 횟수) +1

2. (정수 i/3을 1로 만드는 방법의 횟수) +1

3. (정수 i-1을 1로 만드는 방법의 횟수) +1

 

이 중에서 가장 작은 값을 취하면 된다.

 

2또는 3으로 나누어 떨어지지 않는 수들은 조건을 적절히 빼주면 될 것이다.

---

소스코드

 

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

int min_arr[1000001] = { 0, };

int making_one(int num) {
    for (int i = 1; i <= num; i++) {
        if (i <= 3) //1일 때는 0, 2 or 3일 때는 1이 들어가도록
            min_arr[i] = i / 2;
        else {
            if (i % 2 == 0 && i % 3 == 0) //2와 3으로 나누어 떨어질 때 3개 비교
                min_arr[i] = min(min(min_arr[i / 2], min_arr[i / 3]), min_arr[i - 1]) + 1;
            else if (i % 2 == 0) //2로만 나누어 떨어질 때 2개 비교
                min_arr[i] = min(min_arr[i / 2], min_arr[i - 1]) + 1;
            else if (i % 3 == 0) //3로만 나누어 떨어질 때 2개 비교
                min_arr[i] = min(min_arr[i / 3], min_arr[i - 1]) + 1;
            else //나누어 떨어지지 않을 때
                min_arr[i] = min_arr[i - 1] + 1;
        }
    }
    return min_arr[num];
}

int main() {
    int N;

    cin >> N;
    cout << making_one(N);
}