1463번 : 1로 만들기

Backjoon Online Judge 

"1463번 : 1로 만들기" 문제입니다.

문제 링크 : https://www.acmicpc.net/problem/1463

문제에서 임의의 정수 N에 대해 연산의 최솟값을 구하기 위해 DP를 이용하였습니다. 연산의 경우의 수는 다음 3가지가 존재 합니다.

- 1을 빼기

- 2로 나누기 (나누어 떨어지는 경우)

- 3으로 나누기 (나누어 떨어지는 경우)

 이때 3가지 경우 중 어떤 경우에 연산 경우의 수가 가장 작은지 파악하기 위해 이전값들을 저장합니다. 

 N에서 3가지 연산 결과로 나온 각각의 숫자 중 가장 연산 횟수가 작은 숫자를 만들어내는 연산이 N에 대해 연산을 최소화 할 것입니다.

아래는 코드 설명입니다.

 - 1,000,000이하의 숫자가 주어지므로 배열 크기를 1,000,001로 설정했습니다.

(이 문제의 경우 배열 위치가 해당 숫자가 되고, 그 숫자로 연산하기 때문에 배열 위치랑 숫자랑 맞춰 주었습니다. (연산이 더 간소화됨))

 - 이후 1을 더했을때와 나누기 3을 했을때, 나누기 2를 했을 때 결과를 확인하여 가장 연산이 작아 질 수 있는 숫자를 배열에 저장했습니다.

코드는 C++로 작성하였습니다.

#include <iostream>
#include <algorithm>
 
#define MAX 1000001
 
using namespace std;
 
int main() {
    int N;
    int result[MAX] = { 0, 0 };
    cin >> N;
    for (int i = 2; i <= N; i++) {
        result[i] = result[i - 1] + 1;
        if (i % 3 == 0) {
            result[i] = min(result[i], result[i / 3] + 1);
        }
        else if (i % 2 == 0) {
            result[i] = min(result[i], result[i / 2] + 1);
        }    
    }
    cout << result[N] << endl;
}