백준 1463 1로 만들기 (Java)

1. 문제 링크

1463번: 1로 만들기

 

2. 문제 및 입출력예제

 

3. 문제 풀이

DP 문제인데 하향식으로 풀었다..ㅎㅎ

N부터 3으로 나눠지는 경우, 2로 나눠지는 경우, 그리고 1을 빼는 경우로 해서

그 몫을 배열에 있는 값과 현재 수+1 값과 비교해서 작은 값을 넣는다.

1까지 진행하면서 배열의 1번에 저장된 값을 출력한다.

 

4. 코드

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] num = new int[N+1];
		Arrays.fill(num, Integer.MAX_VALUE);
		num[N] = 0;
		for(int i=N;i>0;i--) { 
			if(i%3==0) {
				num[i/3] = Math.min(num[i/3], num[i]+1); 
			}
			if(i%2==0) {
				num[i/2] = Math.min(num[i/2], num[i]+1);
			}
			num[i-1] = Math.min(num[i-1], num[i]+1);
		}
		System.out.println(num[1]);
	}
}