[백준]1463 - 1로 만들기(Dynamic Programming)

이 문제 역시 Dynamic Programming으로 해결해야 한다.

 

이 문제는 문제 그대로 큰 숫자를 나누고, 빼면서 접근하면 안 된다.

만약 그렇게 한다면 숫자가 3과 2로 나누어 떨어지는지 검사하는 데에만 엄청난 리소스가 낭비된다.

반대로 생각해보자.

 

2로 나누어 떨어지는 수는 2로 나눈 몫의 2배와 같은 값이다.

3으로 나누어 떨어지는 수는 3으로 나눈 몫의 3배와 같은 값이다.

 

그렇다면 역으로 작은 수에 2나 3을 곱하고, 1을 더하면서 숫자를 늘려가면 된다.

 

1부터 시작한다.

1의 3배는 3이다. 한 번의 연산이니 1을 입력한다.

1의 2배는 2이다. 한 번의 연산이니 1을 입력한다.

1+1은 2이다. 그런데 2에는 이미 숫자가 입력되어 있다. 비교 후 더 작은 값을 넣는다.

 

이렇게 하면 배열의 2번째 요소는 1로 결정됐다.

 

마찬가지로 2를 연산한다.

2의 3배는 6이다. 2를 만들기 위한 최소 연산 횟수는 1이니 1을 더 더해서 6에는 2를 입력한다.

2의 2배는 4이다. 마찬가지로 2를 입력한다.

2+1은 3이다. 그런데 3에는 이미 1이 입력되어있다. 1과 2중 1이 더 작은 값이니 1을 그대로 둔다.

 

이와 같이 N을 만들기 위한 최소 연산 횟수를 구하려면 N-1까지 연산을 하면 된다.

 

"우리는 1을 N으로 만드는 게 아니라 N을 1로 만드는 건데요!"

알고 있다. 하지만 위에서 말했듯이 나누어 떨어진다는 것은 그것의 배수라는 뜻이고, 1을 빼서 만들어진다는 것은 1을 더한 값이라는 뜻이다.

1을 N으로 만드는 연산을 역순으로 실행하면 1을 얻을 수 있다.

 

코드는 다음과 같다.

//#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
 
int be1(int N);
 
int main() {
    int N;
    scanf("%d", &N);
    printf("%d\n", be1(N));
}
 
int be1(int N) {
    int* num = new int[N + 1];
    for (int i = 2; i <= N; i++)
        num[i] = TMP_MAX;
    num[1] = 0;
    for (int i = 1; i < N; i++) {
        if (i * 3 <= N && num[i] + 1 < num[i * 3])
            num[i * 3] = num[i] + 1;
        if (i * 2 <= N && num[i] + 1 < num[i * 2])
            num[i * 2] = num[i] + 1;
        if (i + 1 <= N && num[i] + 1 < num[i + 1])
            num[i + 1] = num[i] + 1;
    }
    int re = num[N];
    delete[] num;
    return re;
}

이 포스팅 3줄 정도 쓰기 시작하고부터 갑자기 왼쪽 손목에 힘이 안 들어간다.

왜 이러지.. 오늘 키보드 많이 두드리기는 했는데.. 서서히 이러는 것도 아니고 갑자기 이러네..

손목 받침대도 쓰는데..

오늘은 그만 하고 쉬어야겠다..