[백준]C# 1463번 1로 만들기

[문제]

 

www.acmicpc.net/problem/1463

1463번: 1로 만들기

[ ]

dp [n]  

 n : 2,3 배수 x 
>> min[n-1]+1 

 n : 2의 배수 
>> min[n-1]+1 과 min [n/2]+1중 작은 수 

 n : 3의 배수 
>> min[n-1]+1 과 min [n/3]+1중 작은 수  

 

[의사 코드]

n입력 받음 
n크기의 dp배열 생성 
dp [0]=[1]=0
for(2부터 n까지 반복) 
  dp [i] = dp [i-1]+1
 
  if(2의 배수) min(dp [i] , dp[i/2]+1)
  if(3의 배수) min(dp[i] , dp [i/3]+1) 

dp [n] 출력

 

[코드]

using System;

class dp{
    static void Main(){
        int n = int.Parse(Console.ReadLine());
        int[] dp = new int[n+1];
        dp[0] = dp[1] = 0;
        
        for(int i=2; i<=n; i++){
            dp[i] = dp[i-1]+1;
            
            if(i%2==0){
                dp[i]=Math.Min(dp[i],dp[i/2]+1);
            }
            if(i%3==0){
                dp[i]= Math.Min(dp[i],dp[i/3]+1);
            }
        }
        Console.WriteLine(dp[n]);
    }
}

다른 방법은 이후에 공부하고 와서 다시 해보자.