[백준] 1463 1로 만들기

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

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

이 때 정수N이 주어졌을 때 위 연산 세 개를 적절히 이용해 1로 만들려 한다.

이러한 규칙이 적용되었을 때, 연산을 사용하는 횟수의 최솟값은?

조건: 1보다 크고 10^6보다 작은 정수 1개가 입력된다.

예) 2입력, 1출력  (2-1) 

     10 입력, 3 출력  (10-9-3-1)

나는 이 문제를 다이나믹 프로그래밍으로 풀었다. 문제를 풀기 위한 기법은 BFS 등 여러가지 방법이 있으나, 문제에 접근하기 쉬운 방법으로 풀어 보았다.

몇 가지 예를 들어서 생각해보자.

 

2-1

3-1

4-2-1

5-4-2-1

6-2-1

7-6-2-1

8-4-2-1

9-3-1

10-9-3-1

14-7-6-2-1

2이거나 3일 경우에는 당연히 2나 3으로 나눈다.

4일 경우에는 2로 나누어서 구한다.

5일 경우에는 (2나 3의 배수가 아닐 경우에) -1을 해준 다음 4일 경우에 +1을 한다.

10일 경우에, 10-5-4-2-1 인 경우와 10-9-3-1인 경우가 있다. 

하지만 답은 최소의 횟수 이므로 10-9-3-1 이 정답이다.

여기서 규칙을 잘 찾아보자. N이 1로 되기 위한 최소 횟수를 F(N) 이라고 정의해 보자.

기본적으로 소수나 2,3의 배수가 아닌 경우에는 F(N)=F(N-1)+1 이 된다. (예: 7-6-2-1)

하지만 N이 2나 3의 배수일 경우에는 생각을 다시 해봐야 한다. F(10) 의 기본형이 F(9)+1 이라고 정의하면 F(10) 은 3이 나온다. 하지만 F(10) 을 10-5-4-2-1 의 경우로 나눈 것하고 F(9)+1 하고 무엇이 더 작은지 비교해야 한다. 그러면  F(9)+1 이 더 작으므로 F(10)=F(9)+1 이 된다. 하지만 F(6)의 경우에는 F(5)+1 이랑 6-2-1 이랑 비교했을 때, 6-2-1 이 더 작게 나온다. 그렇다면 여기서 이러한 결과를 도출할 수가 있다. 

F(N)=F(N-1)+1 이 기본형이지만,  N이 2의 배수일 경우 F(N-1)+1 과 F(N/2)+1 을 비교한 것 중 작은것이 정답이고, N이 3의 배수일 경우 F(N-1)+1 과 F(N/3)+1 을 비교한 것 중 작은것이 정답이다. 

이것을 이용하여 간단한 코드를 짜 보았다.

#include <stdio.h>
 
int min(int a,int b)
{
    if(a<=b)
        return a;
    else
        return b;
}
 
int dp(int a)
{
    int arr[1000001]={0};
    if(a==1)
    {
        return arr[0];
    }
    
    for(int i=2;i<=a;i++)
    {
        arr[i]=arr[i-1]+1;
        if(i%2==0)
        {
            arr[i]=min(arr[i],arr[i/2]+1);
        }
        if(i%3==0)
        {
            arr[i]=min(arr[i],arr[i/3]+1);
        }
    }
    
    return arr[a];
}
 
int main()
{
    int a;
    scanf("%d",&a);
    printf("%d",dp(a));
}

이것 외에 bfs를 이용해서 푸는 방법도 있다.

bfs를 이용해 모든 경우의 수를 탐색하고, 답이 나온 곳에서 계산을 멈추고 답을 출력하게 된다. 밑에는 bfs로 푼 문제의 코드이다.

#include <stdio.h>
 
int visit[1000001]={0};
int q[2000000]={0};
int a,front=0,rear=1,ans=1,x;
 
int bfs()
{    
    q[front]=a;
    visit[a]=1;
    
    while(visit[1]==0)
    {
        x=q[front];
        front++;
        if(x%3==0&&visit[x/3]==0)
        {
            visit[x/3]=visit[x]+1;
            q[rear]=x/3;
            rear++;
        }
        
        if(x%2==0&&visit[x/2]==0)
        {
            visit[x/2]=visit[x]+1;
            q[rear]=x/2;
            rear++;
        }
        
        if(visit[x-1]==0)
        {
            visit[x-1]=visit[x]+1;
            q[rear]=x-1;
            rear++;
        }
    }
}
 
int main()
{
    scanf("%d",&a);    
    bfs();    
    printf("%d",visit[1]-1);
}