[백준] 1463번 : 1로 만들기(JAVA)

Long time no see Dynamic programming!

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 14단계

 

동적 계획법 1의 카테고리에 포함되어 있는 문제이다.

 

매우 오랜만에 알고리즘 문제를 풀어본다.

 

마지막으로 푼게 작년이니 말이다...

 

작년이라고 해봤자 약 20일 전이지만 그래도 열심히 문제를 풀지 않았다는 것에 반성하며 글을 작성한다.

 

먼저 1을 1로만드는 최솟값은 0이고, 2를 1로 만드는 값은 1, 3도 1,

 

이제 4부터 3가지 방법으로 나눠서 진행을 시켰다.

 

3가지 방법을 비교할 수 있는 배열을 만들고, 첫 번째 배열에는 2로 나누었을 때, 두 번째는 3으로 나누었을 때,

 

마지막은 1을 뺐을 때 이다.

 

각각 가능하면 compare이라는 배열에 값을 저장 후 맨 마지막에 최솟값을 비교하여 가장 작은 수 를 배열에 저장한다.

 

오랜만에 풀어보는 DP문제 이지만 생각보다 금방 풀어서 기분이 좋다.

 

앞으로도 계속 꾸준히 풀어 이번달 안에 150문제를 달성해야겠다.

 

import java.util.Scanner;

public class Question_1463 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		int[] makeone = new int[N+1];
		
		makeone[1] = 0;
		if(N > 1)
			makeone[2] = 1;
		if(N > 2)
			makeone[3] = 1;
		
		int[] compare = new int[3];
		for(int i = 4; i < N+1; i++) {
			if(i%2 == 0) {
				compare[0] = 1 + makeone[i/2];
			} else {
				compare[0] = 999999;
			}
			if(i%3 == 0) {
				compare[1] = 1 + makeone[i/3];
			} else {
				compare[1] = 999999;
			}
			compare[2] = 1 + makeone[i-1];
			makeone[i] = Math.min(compare[2], Math.min(compare[1], compare[0]));
		}
		
		System.out.println(makeone[N]);
	}

}