[C] 1463: 1로 만들기

맨 처음에는 아예 모든 배열에 미리 수를 찾는 과정으로 만들려고 했고 

 

이때 아래 소스 코드와 같은 방법으로 구현하려고 했지만

 

시간초과가 떠서 실패하였다.

#include <stdio.h>
#include <string.h>

int arr[2][1000001];

void memory(int arr[2][1000001],int n,int cnt)
{
  if(n>1000000)
    return;

      
  if(arr[1][n*3]>cnt ||arr[1][n*3]==0)
  {
    arr[0][n*3]=cnt;
    arr[1][n*3]=cnt;
    memory(arr,n*3,cnt+1);
  }

  
  if(arr[1][n*2]>cnt || arr[1][n*2]==0)
  {
    arr[0][n*2]=cnt;
    arr[1][n*2]=cnt;
    memory(arr,n*2,cnt+1);
  }

  if(arr[1][n+1]>cnt || arr[1][n+1]==0)
  {
    arr[0][n+1]=cnt;
    arr[1][n+1]=cnt;
    memory(arr,n+1,cnt+1);
  }
}

int main(void)
{
  int n;
  scanf("%d",&n);
  
  int cnt=1;
  arr[0][1]=1;
  arr[1][1]=1; //아랫줄이 1이면 이미 계산한거임
  memory(arr,1,cnt);

  printf("%d",arr[0][n]); 
  
}

 

결국 이 알고리즘이 Dynamic Programming 이기 때문에 점화식을 찾는 것이 중요하다고 생각했고

 

결국 3의 배수일때, 2의 배수 일때, 둘 다 아닐때 각각의 점화식을 찾게 되어 아래와 같은 소스코드를 구현하였다

 

또한 bottom-up 구현 중에 어떻게 계산해야 연산횟수가 최소화 되는지 확인하기 위해

 

위의 3가지 경우를 비교하여 가장 최소화한 연산횟수를 배열에 넣었다.

 

이 경우 최대 2*10^6번의 비교가 일어나게 되지만 위의 소스코드는 범위에 넘어가는 범위를 갔다가 return 하므로

 

더욱 비효율적인 코드임을 쉽게 알 수 있다.

 

결국 arr[2*n]=arr[n]+1의 방법이 아닌 

 

arr[n]=arr[n/2]+1의 식을 이용하여 비교횟수및 연산횟수를 범위에 맞게 조정해야한다.

 

#include <stdio.h>
#include <string.h>

int arr[1000001];



int main(void)
{
  int n;
  scanf("%d",&n);
  arr[1]=0;
  for(int k=2;k<=n;k++)
    {
      arr[k]=arr[k-1]+1;
      if(k%3==0)
      {
        if(arr[k]>arr[k/3]+1)
          arr[k]=arr[k/3]+1;
      }
      if(k%2==0)
      {
        if(arr[k]>arr[k/2]+1)
          arr[k]=arr[k/2]+1;
      }
        
    }
  

  printf("%d",arr[n]); 
  
}