[BOJ 1463번/C++] 1로 만들기

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

1463번: 1로 만들기

1로 만들기

문제

문제

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

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

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

 

제한사항

입력

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

출력

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

 

풀이

항상 다이나믹 프로그래밍을 할 때에는 dp배열을 선언했듯이, 이번에도  dp배열을 선언해준다. dp배열의 인덱스는 N이고, 배열의 값은 N을 만드는데 필요한 최소 연산 횟수이다.

 

DP[N] = N을 만드는데 필요한 최소 연산 횟수

 

이후 과정은 각 연산을 한 후, 연산 횟수가 더 작은 값을 저장하는 것이 다이다.

#include <iostream>

using namespace std;

int dp[1000001];
const int INF = 1999999999;

void count(int N, int cnt) {
    if (N == 1) {
        return;
    }

    if (N % 3 == 0 && dp[N / 3] > cnt + 1) {
        dp[N / 3] = cnt + 1;
        count(N / 3, cnt + 1);
    }

    if (N % 2 == 0 && dp[N / 2] > cnt + 1) {
        dp[N / 2] = cnt + 1;
        count(N / 2, cnt + 1);
    }

    if (dp[N - 1] > cnt + 1) {
        dp[N - 1] = cnt + 1;
        count(N - 1, cnt + 1);
    }
}

int main() {
    int N;
    fill_n(dp, 1000001, INF);
    cin >> N;
    dp[N] = 0;

    count(N, 0);

    cout << dp[1] << endl;
    return 0;
}