[백준 1463번/C언어] 1로 만들기, 동적계획법으로 풀이

백준 1463번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 

백준 1473번: https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

문제 내용은 아래와 같습니다. 

 

사실 이전에 업로드한 모든 DP 문제들의 경우, 이 문제에서 막혀 DP에 대해 공부를 시작하면서 풀었던 문제입니다. 이 문제를 접할 당시만 해도 DP에 대한 지식이 없어, 고민을 정말 많이 했는데도 답이 나오지 않던 중, DP로 접근해서 풀어야 하는 문제임을 깨닫고, 더 쉬운 DP 문제부터 시작하여 다시 여기까지 와서 풀게 되었습니다.

DP 개념을 모를 경우 풀기 쉽지 않으니, 동적계획법 학습을 먼저 하시기를 추천드립니다. 또한 제 블로그에 다른 DP 문제들 풀이가 나와있으니, 먼저 풀고 이 문제를 시도하시는 것도 좋을 것 같습니다. 동적계획법에 대한 기본적인 설명은 아래 블로그에 잘 설명되어 있으니 참고해 주세요.

https://didu-story.tistory.com/220

[알고리즘] Dynamic Programming (동적 계획법, DP) (feat. Swift 스위프트)

 

동적계획법을 이용하기 위해서는, 동적계획법의 핵심인 점화식을 우선적으로 파악해야 합니다. 사실 점화식을 세워야겠다는 인식만 있으면 이 문제는 어렵지 않게 풀립니다. 우선 네 가지 경우로 나눠준 후에, 경우에 맞게 점화식을 세우면 되는데, 경우에 따른 점화식은 다음과 같습니다. 

(case1: x가 2와 3의 배수인 경우) C(x) = C(x/6) + 2 || C(x/2) + 1 || C(x/3) + 1 || C(x-1) + 1 중 가장 작은 값
(case2: x가 3의 배수인 경우) C(x) = C(x/3) + 1 || C(x-1) + 1 중 작은 값
(case3: x가 2의 배수인 경우) C(x) = C(x/2) + 1 || C(x-1) + 1 중 작은 값
(case4: x가 2와 3의 배수가 아닌 경우) C(x) = C(x-1) + 1

첫 번째 경우는 x가 2와 3 모두의 배수인 경우 (즉, 6의 배수인 경우)입니다. 이 때는

x에 6을 나눈 수가 연산에 사용하는 횟수에 2를 더한 값 (2를 더하는 이유는 2로 나누고 3으로 나누는 횟수를 더한 것)
x에 2를 나눈 수가 연산에 사용하는 횟수에 1을 더한 값 (1을 더하는 이유는 2로 나누는 횟수를 더한 것)
x에 3을 나눈 수가 연산에 사용하는 횟수에 1을 더한 값
x에 1을 뺀 수가 연산에 사용하는 횟수에 1을 더한 값

이렇게 네 가지 경우 중 가장 작은 값이 x의 연산에 필요한 횟수가 됩니다. 두 번째 경우부터는 위 경우에서 각각 맞는 점화식을 가져다 쓰면 됩니다.

 

이렇게  세운 점화식을 바탕으로 코드를 구성하면 다음과 같습니다. 

#include <stdio.h>
#include <stdlib.h>

// 정수 두 개를 인자로 받아 더 작은 수를 return하는 함수
int compare(int a, int b) {
    if (a > b) return b;
    else return a;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int *res = (int *)malloc(sizeof(int) * (n+1));
    res[0] = 0;
    res[1] = 0;
    
    for (int i = 2; i <= n; i++) {
        if (i % 6 == 0) { // case1
            res[i] = compare(res[i/6]+2, res[i-1]+1);
            res[i] = compare(res[i], res[i/3]+1);
            res[i] = compare(res[i], res[i/2]+1);
        }
        else if (i % 3 == 0) res[i] = compare(res[i-1], res[i/3]) + 1;  // case2
        else if (i % 2 == 0) res[i] = compare(res[i-1], res[i/2]) + 1;  // case3
        else res[i] = res[i-1] + 1;  // case4
    }
    
    printf("%d", res[n]);
    free(res);
}

 

 

추가적으로 제가 유용하게 썼던 반례가 나와있는 백준 질문게시판 링크 첨부합니다.

https://www.acmicpc.net/board/view/125922