[백준] 1463번: 1로 만들기 - C++

문제

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

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

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

 

입력

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

 

출력

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

---

DP를 이용하여 풀 수 있는 문제.

 

1. N이 3으로 나누어 떨어지면, 3으로 나눈다 ➡️ D[N] = D[N/3] + 1

2. N이 2로 나누어 떨어지면, 2로 나눈다 ➡️ D[N] = D[N/2] + 1

3. 1을 뺀다 ➡️ D[N] = D[N - 1] + 1

 

그러나 여기서 주어진 규칙대로 풀다보면 틀릴 수 있기 때문에 한번 더 생각을 해줘야 한다.

10의 경우, 나눠 떨어지는 대로 풀면 10->5->4->2->1 로 4가 출력될 수 있지만, 답은 10->9->3->1 로 3이다.

 

10과 같은 경우를 생각해서 1을 먼저 빼준 뒤 연산하는 경우가 더 작은지, 원래 값에서 연산을 해주는 경우가 더 작은지 비교를 하며 풀어줘야한다.

문제를 풀 때 아직 bottom-up 방식을 공부하지 않았을 때여서, top-down 방식으로 풀었다.

 

코드

#include <cstdio>
#include <vector>
#define MAX 1000001

using namespace std;

vector<int> memo(MAX, -1);
int DP(int num);

int main(void) {
    int num;
    scanf("%d", &num);
    printf("%d\n", DP(num));
    return 0;
}

int DP(int num) {
    if(num == 1) return 0;
    if(memo[num] != -1) {
        return memo[num];
    }

    memo[num] = DP(num - 1) + 1;

    if(num % 3 == 0) {
        memo[num] = (DP(num / 3) + 1) < memo[num] ? DP(num / 3) + 1 : memo[num];
    }
    if (num % 2 == 0) {
        memo[num] = (DP(num / 2) + 1) < memo[num] ? DP(num / 2) + 1 : memo[num];
    }
    return memo[num];
}

 

+) 2022.02.10 추가

bottom-up 방식으로도 풀어보았다. 보면 알겠지만 접근방법도, 수식도 동일하게 풀어주되, 재귀에서 반복문으로만 바꿔주면 된다.

코드(2)

#include <cstdio>
#define MAX 1000001

int DP(int num);
int min(int a, int b) {
    return a < b ? a : b;
}

int main(void) {
    int n;
    scanf("%d", &n);

    printf("%d\n", DP(n));
    return 0;
}

int DP(int num) {
    int memo[MAX];

    for(int i = 2; i <= num; i++) {
        memo[i] = memo[i - 1] + 1;

        if(i % 3 == 0) {
            memo[i] = min(memo[i], memo[i / 3] + 1);
        }
        if(i % 2 == 0) {
            memo[i] = min(memo[i], memo[i / 2] + 1);
        }
    }

    return memo[num];
}