1463번: 1로 만들기

1463번: 분산 처리(BOJ C/C++)

사용 언어: C

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

첫 번째 풀이

시간 제한 때문에 이 풀이로 풀면 TLE가 발생할 것을 알면서도 그냥 만들고 싶어서 코드를 구현했다.

#include <stdio.h>

int main(void)
{
    int N;
    int cnt=0;
    scanf("%d",&N);
    while(N!=1)
    {
        int tmp = N-1;
        if(N%3==0)
        {
            N/=3; cnt++;
            continue;
        }
        else if(tmp%3==0)
        {
            N-=1; cnt++;
            N/=3; cnt++;
        }
        else if(N%2==0)
        {
            N/=2; cnt++;
            continue;
        }
    }
    printf("%d\n",cnt);
    return 0;
}

 

 

두 번째 풀이

이런 류의 문제는 어떻게 풀어야할지 잘 몰라서 다른 분들의 풀이를 참고해본 결과, 매우 단순했다. 입력한 숫자의 위치에 답을 입력하는 배열을 만드는 것이다. 과정은 코드를 보면 이해되는데, 부가적인 설명으로 N=4을 예시로 들면, arr[4]을 도출하기 위해서는 arr[0], arr[1], arr[2], arr[3]의 값이 있으면 된다. 두 가지로 나눠서 생각해야하는데, arr[4]를 만드려면 arr[2]를 만들기 위해 필요한 경우에 +1을 하는 것이다. 그런데, arr[2]의 값에서 +1을 하는 경우의 값보다 arr[3]의 값에서 +1을 하는 값이 더 작을 수도 있다. arr[4]를 만드려면 4에서 1을 뺀 값인 3을 만들 수 있으므로 arr[i]=arr[i-1]+1은 항상 성립한다. 결론적으로 arr[i]=arr[i-1]+1에서 arr[i]의 값과 i의 값에 2 혹은 3으로 나눠서 +1을 더한 값을 비교해서 더 작은 값을 받으면 그게 닶이다.

#include <stdio.h>
#define MAX 1000001

int N;
int arr[MAX];

int MIN(int a, int b)
{
    return a < b ? a : b;
}

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