[Java] 백준 1463번 1로 만들기 (DP)

[Java]  백준 1463번 1로 만들기 (DP)

* 학습 목적의 게시물이나 혹시 이 게시물이 문제가 된다면 언제든 연락 부탁드립니다.

* 더 나은 풀이를 위한 훈수, 조언 등 모두 환영합니다!

□ 문 제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

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

○ 입 력

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

○  출 력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

[문제 링크] 백준 1463번 1로 만들기

---

□ 문제풀이

주어진 세 가지 연산으로 확인해야 할 조건은 아래 4가지 이다.

1. 정수 X가 6으로 나누어 떨어질 경우
   • 정수 X 연산 횟수의 최솟값은 X / 3, X / 2, X - 1 이 세 수의 연산 횟수 중에 가장 작은 값에서 1을 더한 값이다.
2. 정수 X가 3으로만 나누어 떨어질 경우
   • 정수 X 연산 횟수의 최솟값은 X / 3, X - 1 이 두 수의 연산 횟수 중에 가장 작은 값에서 1을 더한 값이다.
3. 정수 X가 2로만 나누어 떨어질 경우
   • 정수 X 연산 횟수의 최솟값은 X / 2, X - 1 이 두 수의 연산 횟수 중에 가장 작은 값에서 1을 더한 값이다.
4. 위 경우에 모두 해당하지 않을 경우
   • 정수 X 연산 횟수의 최솟값은 X - 1의 연산 횟수에서 1을 더한 값이다.

위 조건으로 동적 계획법을 적용해 풀 수 있다.

□ 참고사항

• 추가 공부 필요내용 : 동적 프로그래밍, 분할 정복

□ 전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class B1463 {
	
	static int num, answer;
	static int[] dp;
	static final int MAXNUM = 1000000;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		num = Integer.parseInt(br.readLine());
		
		dp = new int[MAXNUM + 1];
		dp[2] = 1;
		dp[3] = 1;
//		answer = bottomUp(num);
		answer = topDown(num);
		
		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
		br.close();
	}
	
	static int topDown(int n) {
		if(n < 3) {
			return dp[n];
		} else if(dp[n] > 1){
			return dp[n];
		} else{
			if(n % 6 == 0) {
				return dp[n] = Math.min(topDown(n / 3), Math.min(topDown(n / 2), topDown(n - 1))) + 1;
			} else if(n % 3 == 0) {
				return dp[n] = Math.min(topDown(n / 3), topDown(n - 1)) + 1;
			} else if(n % 2 == 0) {
				return dp[n] = Math.min(topDown(n / 2), topDown(n - 1)) + 1;
			} else {
				return dp[n] = topDown(n - 1) + 1;
			}
		}
	}
	
	static int bottomUp(int n) {
		if(n > 3) {
			for(int i = 4; i <= n; i++) {
				if(i % 6 == 0) {
					dp[i] = Math.min(dp[i / 3], Math.min(dp[i / 2], dp[i - 1])) + 1;
				} else if(i % 3 == 0) {
					dp[i] = Math.min(dp[i / 3], dp[i - 1]) + 1;
				} else if(i % 2 == 0) {
					dp[i] = Math.min(dp[i / 2], dp[i - 1]) + 1;
				} else {
					dp[i] = dp[i - 1] + 1;
				}
			}
		}
		return dp[n];			
	}
}