[BAEKJOON 백준] 1463 1로 만들기

www.acmicpc.net/problem/1463

1463번: 1로 만들기

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

 

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

 

입력되는 X 값을 이용을 해서 X+1의 크기를 가지는 배열을 만들어 준다.

 

그렇게 만들어진 배열을 이용을 해서 2번칸부터 몇번 나눠야 하는지 넣어주는 방식이다.

 

예를들어 2부터 시작을 하면 2로 나누면 1이나오기 때문에 2번칸에 1이 들어가고, 3또한 3으로 나눠 1이 되기 때문에 1이들어간다.

4의 경우 2로 나눴을때 2가 되고, 거기에 1일 빼서 1이 되기때문에 두번의 과정을 거치기 때문에 2가 들어간다.

5의 경우 2로도 3으로도 나눠지지가 않아 -1을 해주는 과정을 거친다. 그런데 -1을 하면서 4가 되는데 4에서 1이 될때 2가 되므로 2에 1을 더해서 5가 1일 될때는 1이 되는 것이다.

이러한 방식으로 코드를 작성했다.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		int X= sc.nextInt();
		int memo[]=new int[X+1];
		
		memo[0]=0;
		memo[1]=0;
		int min=0;
		for (int i = 2; i <= X; i++) {
			min=Integer.MAX_VALUE;
			if(i%3==0&&1+memo[i/3]<min) min=1+memo[i/3];
			if(i%2==0&&1+memo[i/2]<min) min=1+memo[i/2];
			if(1+memo[i-1]<min) min=1+memo[i-1];
			
			memo[i]=min;
		}
		sc.close();
		System.out.println(memo[X]);
	}
}