[백준 1463, c++] 1로 만들기(dp)

문제 번호

• 1463(https://www.acmicpc.net/problem/1463)

문제 및 입/출력

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

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

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

 

입력

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

 

출력

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

 

예제 입력1

2

예제 출력1

1

예제 입력2

10

예제 출력2

3

ex> 10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

문제 풀이

문제에서 제안하는 세가지 연산을 적절히 사용해서 결과 값 1을 만들려고하는데 연산을 사용하는 횟수의 최솟값을 출력하는 문제이다.

 

• DP(Dynamic Programming)을 이용하여 풀었다. 여기서 말하는 [DP, 동적 프로그래밍]이란 큰 문제를 작은 문제로 분할하여 문제를 푸는 방법이다. 
• 이 방법을 사용하는 이유는, 큰 문제가 작은 문제를 포함하는 구조를 갖고 있을 때, 작은 문제를 알면 큰 문제의 정답을 빠르게 구할 수 있다는 점이다.
• top-down의 재귀 방식이 아닌 bottom-up의 반복문 방식을 사용하여 풀었다.
• 첫번째 연산(3으로 나누었을때 나머지가 0이면): D(N) = D(N/3) + 1
• 두번째 연산(2로 나누었을때 나머지가 0이면): D(N) = D(N/2) + 1
• 세번째 연산: D(N) = D(N-1) + 1

---

1. 정수 x을 입력받는다.
2. 정수 x라는 큰 문제를 해결하기위해 이 문제를 작은 문제로 분할한다. 가장 빠르게 알 수 있는 것은 입력이 1일때는 연산을 사용하지 않아도 되므로 결과 값이 0이라는 것이다. 즉, arr[1] = 0; (arr[입력] = 연산 사용 횟수) 이 된다.
3. 다음으로는 2부터 정수 x까지 입력으로 넣어서 각각의 연산을 사용하였을 때의 출력 값(=연산 사용 횟수)가 가장 작은 값으로 설정한다.
4. 순차적으로 x까지 계산하게 되고 x를 입력으로 하였을때의 연산 횟수를 출력한다.

소스 코드

#include <iostream>
#include <stdio.h>
 
using namespace std;
 
#define MAX 1000000
 
int min(int a, int b) {
    if (a > b) return b; return a;
}
 
int arr[MAX + 1];
 
int main() {
    int x;
    scanf("%d", &x);
 
    arr[1] = 0;
    for (int i = 2; i <= x; i++) {
        arr[i] = arr[i - 1] + 1;
        if (!(i % 2)) {
            arr[i] = min(arr[i], arr[i / 2] + 1);
        }
        if (!(i % 3)) {
            arr[i] = min(arr[i], arr[i / 3] + 1);
        }
    }
 
    printf("%d\n", arr[x]);
    return 0;
}