[백준 1463] 1로 만들기

[백준 1463] 1로 만들기

문제 출처 : https://www.acmicpc.net/problem/1463

---

문제

---

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

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

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

1을 뺀다.

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

입력

---

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

출력

---

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

예제 입력

10

예제 출력

3

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

• 문제 이해하기

처음에 주어진 숫자를, 3가지 규칙을 이용해서 1로 만드는 데 최소 횟수 값을 구하는 문제다. 규칙은 2로 나누어질 때, 3으로 나누어질 때 그리고 이 두가지에 해당이 안되면 1로 빼는 것으로 되어있다.

우리는 최소 횟수 값을 구하면 되기 때문에, 한번의 연산이 진행 될 때 마다 1씩 더해주는 것으로 최소 횟수를 구하면 되지 않을까 생각했다.

하지만 그냥 1을 더해주는 식으로 끝낼 순 없다.

10 -> 5 -> 4 -> 2 -> 1
10 -> 9 -> 3 -> 1

위처럼 10으로 값을 구할 때, 두가지 경우로 나누어지는 모습을 볼 수 있다.

따라서 과정 중에 최소를 비교할 수 있는 함수 또한 필요할 것이라고 생각했다.

• 계획 및 문제 해결

우선 처음에 입력되는 수는 1 이상 100만 이하의 수다. 따라서 값을 넣을 배열의 크기를 arr_num[1000001]로 잡고 시작했다.

우리는 이 arr_num 배열 안에 들어가는 숫자마다, 그 숫자가 1로 되기까지의 최소 횟수가 값으로 나오도록 만들어야 한다.

따라서 입력 수는 1부터 시작하기 때문에 arr_num[0]은 필요가 없다. 또한 arr_num[1]은 이미 1이기 때문에 1로 만들 필요가 없다. 그래서 0이라고 미리 만들어주고 시작해야한다.

arr_num[1] = 0;

이제 우리는 arr_num[2]의 값부터 그 이상의 수가 들어와도 횟수를 구할 수 있는 방법을 찾아야 한다.

즉 내가 구하고 싶은 수를 N이라고 할 때, 결국 arr_num[N]의 값으로 답이 나오도록 만들면 된다.

결과값 출력

cout << arr_num[N];

arr_num[1]의 값은 초기화를 해주었기 때문에 2~N까지 반복문을 통해서 값을 얻어야 한다.

우리는 총 3가지 규칙을 다음과 같이 작성한다.

1. 2로 나눈다 (arr_num[i / 2] + 1) // 여기서 + 1은 연산을 한 횟수이다.

arr_num[i] = min(arr_num[i], arr_num[i / 2] + 1);

기존의 값과 2로 나눈 값의 최소값을 비교하여 대입한다.

2. 3으로 나눈다 (arr_num[i / 3] + 1)

arr_num[i] = min(arr_num[i], arr_num[i / 3] + 1);

기존의 값과 3으로 나눈 값의 최소값을 비교하여 대입한다.

3. 1을 뺀다.

arr_num[i] = arr_num[i - 1] + 1; 

-> 1을 뺀 값의 배열 + 한번 시행한 횟수

이제 반복문에서, 2와 3으로 나누어지는 경우를 if문으로 만들어주면 반복문 i의 값이 들어왔을 때 해당하는 구역으로 들어가게 된다.

for (int i = 2; i <= N; i++)
{
    arr_num[i] = arr_num[i - 1] + 1; // 1을 빼야할 때
    if (i % 2 == 0) { // 2로 나누어질 때
        arr_num[i] = min(arr_num[i], arr_num[i / 2] + 1);
    }
    if (i % 3 == 0) { // 3으로 나누어질 때
        arr_num[i] = min(arr_num[i], arr_num[i / 3] + 1);
    }
}

따라서 마지막에 arr_num[N]만 출력해주면 값을 구할 수 있게 된다.

• 전체 소스 코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int arr_num[1000001]; //10^6까지 자연수를 나타내기 위한 배열
 
 
/*
int min(int a, int b) { // 연산 사용 횟수 최소값을 구하기 위한 함수
    return a > b ? b : a;
}
*/
 
 
int main(void) {
 
    int N;
    cin >> N; //자연수 N 입력
 
    arr_num[1] = 0; // 자연수 1을 만들어야 되기 때문에, 1은 0이라고 놓자.
 
    for (int i = 2; i <= N; i++)
    {
        arr_num[i] = arr_num[i - 1] + 1; // 1을 빼야할 때
 
        if (i % 2 == 0) { // 2로 나누어질 때
            arr_num[i] = min(arr_num[i], arr_num[i / 2] + 1);
        }
        if (i % 3 == 0) { // 3으로 나누어질 때
            arr_num[i] = min(arr_num[i], arr_num[i / 3] + 1);
        }
    }
 
    cout << arr_num[N];
 
    return 0;
}