[백준/C언어] 1463번 - 1로 만들기

백준 웹사이트 "1463번 - 1로 만들기" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

1463번: 1로 만들기

---

소스 코드

#include <stdio.h>

int min(int a, int b);

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

    int num[N+1];   //num[n]: n을 1로 만드는 데 필요한 연산의 횟수
    num[0]=0, num[1]=0;
    //printf("num[%d]: %d\nnum[%d]: %d\n", 0, num[0], 1, num[1]);

    for(int i=2; i<=N; i++){
        int minimum = num[i-1] + 1;
        if(i%3==0){
            minimum = min(minimum, num[i/3]+1);
        }
        if(i%2==0){
            minimum = min(minimum, num[i/2]+1);
        }
        num[i] = minimum;
        //printf("num[%d]: %d\n", i, num[i]);
    }

    printf("%d\n", num[N]);
}

int min(int a, int b){
    if(a<b)
        return a;
    else
        return b;
}

---

문제 풀이

  'num[n]'은 숫자 n을 1로 만드는 데 필요한 연산의 횟수입니다. 동적 계획법을 이용하여 각 수를 1로 만드는 연산의 횟수를 기록하는 것이 핵심이며, 점화식은 다음과 같습니다.

$$ num[i] = min(num[i-1], num[i/3], num[i/2])+1 $$

  숫자 i에 대해 num[i]를 구하기 위해, num[i-1], num[i/3], num[i/2]를 비교하여 그 중 최솟값에 1을 더하면 되는 셈이죠. 하지만 이 점화식에 틀린 점이 있습니다. 바로 num[i/3]과 num[i/2]는 각각 i가 3으로 나누어떨어질 때, i가 2로 나누어 떨어질 때만 고려해줘야 한다는 것입니다. 이러한 조건까지 고려하여, 아래와 같이 동적 계획법을 시행하면 됩니다.

 

for(int i=2; i<=N; i++){
    int minimum = num[i-1] + 1;
    if(i%3==0){
        minimum = min(minimum, num[i/3]+1);
    }
    if(i%2==0){
        minimum = min(minimum, num[i/2]+1);
    }
    num[i] = minimum;
    //printf("num[%d]: %d\n", i, num[i]);
}

 

위와 같은 for문을 거치면, 배열 'num'에는 각 숫자를 1로 만드는 연산 횟수의 최솟값이 저장됩니다. 마지막으로 정수 N을 1로 만드는 연산 횟수의 최솟값은 'num[N]'을 출력함으로써 얻을 수 있습니다.