[다이나믹프로그래밍] 백준 : 1로만들기(1463번)

import java.util.Scanner;
public class Main {
static final int MC = 1000001; //충분히 큰 수
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] dp = new int[N+1];
int[] tempt = new int[3];
int count;
if(N > 2)
{
dp[1] = 0;
dp[2] = 1;
dp[3] = 1;
for(int i = 4; i<dp.length; i++)
{
count = 0;
tempt = inicial(tempt);
if(i%3 ==0)
tempt[count++] = dp[i/3];
if(i%2 ==0)
tempt[count++] = dp[i/2];
tempt[count] = dp[i-1];
dp[i] = min(tempt)+1;
}
System.out.println(dp[N]);
}
else if(N == 2)
System.out.println(1);
else
System.out.println(0);
}
public static int min(int[] arr) {
int result = arr[0];
for(int i = 1; i<arr.length; i++)
{
if(arr[i]<result)
result = arr[i];
}
return result;
}
public static int[] inicial(int[] arr) {
for(int i = 0; i<arr.length; i++)
arr[i] = MC;
return arr;
}
}
view raw Main.java hosted with ❤ by GitHub

댓글

가장 많이 본 글