백준 1463번 "1로 만들기"

백준 1463번 “1로 만들기”

Question:

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

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

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

Input:

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

Output:

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

Restriction:

시간제한:
0.15 초

Example Case:

Input case 1:

2

Output case 1:

1

Input case 2:

10

Output case 2:

3

풀이 과정:
이 문제는,
Dynamic Programming(DP)를 이용하여 풀 수 있는 문제이다.

정수 N에 대하여,
문제 조건에 대해 구현할 수 있는 연산이 3가지가 존재한다.

N에 대하여 N-1,N/2,N/3 총 세가지의 연산을 할 수 있다.

문제는,
이 세 연산을 활용하여 N(N>=1)을 1로 만들어야하는데,
또한 1로 만들 시의 연산 횟수가 최솟값이 되어야한다.

그렇다면 간단히 예시를 들어보자.

ex.N = 4 일때,

1. N은 2로 나눴을 때 나머지가 0이다. 따라서 2로 나눌 수 있고 연산을 적용하면 4 -> 2 -> 1 이다.(연산 2번.2로 나누기 + 2로 나누기).
2. N에서 1을 빼게 되면,(연산 1번) N은 3이 되고 3으로 나눴을 때 나머지가 0이다. 따라서 3으로 나누게 되면 1로 만들어진다. 4 -> 3 -> 1 이다.(연산 총 2번.1 빼기 + 3로 나누기).

이 처럼 정수 N에 대하여,
2나 3으로 나누어 떨어질 때 나누기 연산을 통한 연산의 최솟값과,
1로 빼고 나서의 연산의 최솟값.
이 둘중의 최솟값이 정수 N에 대한 연산의 최솟값이 된다.

코드를 살펴보자.

코드상에서는
dp[i/2],dp[i/3],dp[i-1] 처럼,
dp의 특징인 작은 경우의 해답을 재이용하는 모습을 보여주고 있다.

ex) N = 4
4 -> 2 -> 1 이면,
결국 N = 4 일 때는 N = 2 일 때의 연산의 최솟값을 이용한다.

ex 2) N = 10
10 -> 9 -> 3 -> 1 이면,
결국 N = 10 일 때는 N = 9 일 때의 연산의 최솟값을 이용한다.

#include <iostream>
#include <algorithm>

using namespace std;

int dp[1000001];

int main() {
    int n; // input
    cin >> n;
    for(int i = 2;i<1000001;i++) {
        dp[i] = dp[i-1] + 1; 
        // 1로 빼는 연산,이전 N의 연산 최솟값 이용.
        if(i%2== 0) {
            dp[i] = min(dp[i],dp[i/2]+1);
            //이전 N의 연산 최솟값과 2로 나누어질 때의 연산- 둘중의 최솟값
        }
        if(i%3 == 0) {
            dp[i] = min(dp[i],dp[i/3]+1);
            //이전 N의 연산 최솟값과 3로 나누어질 때의 연산- 둘중의 최솟값
        }
    }
    cout << dp[n] << endl;
    return 0;
}

• 백준
• 문제풀이
• 알고리즘