[백준] 1463번: 1로 만들기 (C언어)

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

1463번: 1로 만들기

 

난이도: solved.ac 실버 3

 

 

매우 유명한 dp문제다

 

arr[N]을 N→1로 만드는데 필요한 연산의 최소 횟수라고 해보자

 

arr[N]은 다음 3개의 값 중 최소값이 된다

 

• arr[N / 3] + 1 (N이 3으로 나누어 떨어지는 경우)
• arr[N / 2] + 1 (N이 2으로 나누어 떨어지는 경우)
• arr[N - 1] + 1

이를 코드로 나타내면 다음과 같다

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define min(A,B) A<B?A:B

int arr[1000001];

int main() {
    int X;
    scanf("%d", &X);
    for (int i = 2; i <= X; i++) {
        arr[i] = arr[i - 1] + 1;
        if (i % 3 == 0)
            arr[i] = min(arr[i], arr[i / 3] + 1);
        if (i % 2 == 0)
            arr[i] = min(arr[i], arr[i / 2] + 1);
    }
    printf("%d", arr[X]);
	return 0;
}