[BAEKJOON ONLINE JUDGE 1463번] 1로 만들기

1로 만들기 in C++

문제

• 어떠한 정수 X에 아래 3개의 연산을 통해 1을 가장 빠르게(연산의 횟수를 최소화 하여) 만드려고 한다.
  • X가 3으로 나누어 떨어지면, 3으로 나눈다.
  • X가 2로 나누어 떨어지면, 2로 나눈다.
  • 1을 뺀다.
• X를 1로 만들기 위해 연산이 가장 적게 사용된 횟수를 출력하도록 한다.
• 예시
  • N=1 일 때, 연산의 횟수는 0, N=2 일 때, 연산의 횟수는 2->1 이므로 1. N=3 일 때, 연산의 횟수는 3->1 이므로 1.
  • N=4 일 때, 연산의 횟수는 4->3->1 or 4->2->1 두 가지 경우 모두 2.
  • … N=10 일 때, 10->5->4->2->1의 경우에는 4이지만, 10->9->3->1의 경우에 3이므로 이 때는 3.

입력 데이터

• 1보다 크거나 같고 106보다 작은 정수 N
• 입력 예

10

출력 데이터

• 연산이 사용된 횟수
• 출력 예

3

해결 방법

• N이 1, 2, 3일 때는 필요한 연산의 최소 횟수는 각각 0, 1, 1이다. N이 4이상인 경우부터 수에 1을 빼거나, 2나 3을 나누는 연산을 통해 더 작은 수를 만들어서, 만들어진 수를 1로 만들면 된다.
• 예를 들어, N=10인 경우는 10->9->3->1이 최소한의 연산을 이용한 경우인데, 3을 1로 만드는데 필요한 연산의 수는 1이고, 9를 1로 만드는데 필요한 연산의 수는 8(=9-1)을 1로 만드는데 필요한 연산의 수 보다 3(=9/3)을 1로 만드는데 필요한 연산의 수가 더 적으므로 이 방법을 선택한 것이다.
• 즉, 입력된 수 N 이전의 수를 1로 만드는 방법을 어딘가에 저장해 둔다면, 이를 이용하여 쉽게 N을 1로 만드는 방법을 구할 수 있는 것이다.

코드

#include <iostream>
using namespace std;

int main()
{
    int N; // 입력받을 N
    cin >> N;

    int count[1000001] = {0}; // N을 1로 만드는데 필요한 연산의 최소 횟수를 저장할 배열(count[N]에 저장됨)
    count[2] = 1; // 2->1 이므로 count[2]=1
    count[3] = 1; // 3->1 이므로 count[3]=1

    for(int i = 4; i <= N; i++) // N >= 4 인 경우의 알고리즘
    {
        int minCount = 0; // i를 1로 만드는데 필요한 최소 연산 횟수-1(4부터 '4이전의 수를 1로 만드는 방법+1'이 그 수를 1로 만드는 방법)

        if(i % 3 == 0 && i % 2 == 0) // i가 6의 배수(2와 3으로 모두 나누어 떨어지는 수)인 경우
        { // i/3을 1로 만드는 경우와 i/2를 1로 만드는 경우 중, 연산의 횟수가 적은 경우를 minCount로 지정
            if(count[i / 3] < count[i / 2]) minCount = count[i / 3];
            else minCount = count[i / 2];
        }
        else if(i % 3 == 0 && i % 2 != 0) // i가 3의 배수인 경우
        { // i/3을 1로 만드는 경우와 i-1를 1로 만드는 경우 중, 연산의 횟수가 적은 경우를 minCount로 지정
            if(count[i / 3] < count[i - 1]) minCount = count[i / 3];
            else minCount = count[i - 1];
        }
        else if(i % 3 != 0 && i % 2 == 0) // i가 2의 배수인 경우
        { // i/2을 1로 만드는 경우와 i-1를 1로 만드는 경우 중, 연산의 횟수가 적은 경우를 minCount로 지정
            if(count[i / 2] < count[i - 1]) minCount = count[i / 2];
            else minCount = count[i - 1];
        }
        else // i가 3의 배수가 아닌 홀수인 경우
            minCount = count[i - 1]; // i-1을 1로 만드는 방법이 minCount임

        count[i] = minCount + 1; // minCount+1이 i를 1로 만드는데 필요한 연산의 최소 횟수
    }

    cout << count[N] << endl;

    return 0;
}

문제 원본 링크

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