BOJ - 1463번 1로 만들기

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

1463번: 1로 만들기

 

 

정수가 주어졌을 때 1을 만드는 연산의 최소횟수를 구하는 문제다.

 

연산의 종류는 다음과 같다.

 

1. 3의 배수면 3으로 나눌 수 있다.
2. 2의 배수면 2로 나눌 수 있다.
3. 1을 뺄 수 있다.

 

간단하게 생각할 수 있다.

 

어떤 수 N에 대해서 1을 빼거나 2로 나누거나 3으로 나누거나 해보자.

 

min_1 = N-1
div_2 = N/2
div_3 = N/3

 

이라고 생각하면 결국에 또 min_1도 위와같은 방식으로 1로 만들어야 할거고 div_2도, div_3도 1로 만들어야 한다.

 

작은 수부터 미리 계산했었다면

 

min(min_1을 1로 만드는 횟수, div_2를 1로 만드는 횟수, div_3을 1로 만드는 횟수) + 1

 

이 N을 1로 만드는 최소 횟수일 것이다.

 

 

/* BOJ - 1463번 1로 만들기 문제 다시풀기 */

#include <stdio.h>

int DP[1000001];

// 초기화 함수
void init() {
    for (int i = 0; i < 1000001; i++) DP[i] = 0;
}

// 계산 함수
void cal() {
    int div_3, div_2, min_1, i, min;

    for (i = 2; i < 1000001; i++) {
        min_1 = DP[i - 1] + 1;
        if (i % 2 == 0) div_2 = DP[i / 2] + 1;
        else div_2 = min_1 + 1;
        if (i % 3 == 0) div_3 = DP[i / 3] + 1;
        else div_3 = min_1 + 1;

        min = min_1;
        if (min > div_2) min = div_2;
        if (min > div_3) min = div_3;
        DP[i] = min;
    }
}

int main()
{
    int N;
    scanf("%d", &N);
    init();
    cal();
    printf("%d\n", DP[N]);
    return 0;
}