[백준]1463. 1로 만들기

[문제]

www.acmicpc.net/problem/1463

1463번: 1로 만들기

[풀이]

DP를 사용해서 2부터 N까지의 1을 만들 때 필요한 연산의 최소 횟수를 구했다.

bottom-up 방식을 사용해 2부터 N까지의 최솟 값을 구했다.

 

연산은 아래와 같이 3가지 연산이 있다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

따라서 1을 빼는 연산은 모든 숫자에 대해 가능하므로 구하고 

X가 2로 나눠지는 경우, 3으로 나눠지는 경우에는 이에 대한 경우도 구해서 최솟 값을 구했다.

 

 

[코드]

 

시간 : 4ms

#include <stdio.h>
#define MAX 1000001


int MIN(int a, int b)
{
    if(a>b )    return b;
    else    return a;
}

int main(void)
{
    int N;
    int DP[MAX]={0,};
    
    scanf("%d",&N);
    
    for(int i=2;i<=N;i++)
    {
        DP[i] = DP[i-1]+1;
        if(i%2 == 0)    DP[i] = MIN(DP[i], DP[i/2]+1);
        if(i%3 == 0)    DP[i] = MIN(DP[i], DP[i/3]+1);
    }
    printf("%d",DP[N]);
    return 0;
    
}