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

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

1463번: 1로 만들기

 

 

dp에는 두 종류가 있다.
나는 이번에 Bottom-up을 사용해서 풀어봤다.

1. Bottom-up   :   반복문을 이용하여 풀이
2. Top-down    :   재귀를 이용하여 풀이

 

 

- 먼저 1을 빼보고 계산을 한다.
- 만약 3으로 나누어진다면, 1로 뺀것과 어느게 더 작은지 비교
- 만약 2로 나누어진다면, 1로 뺀것과 어느게 더 작은지 비교

 

dp[1]은 어차피 0이므로 따로 초기화 하지 않고,
dp[2]부터 반복문을 돌아 dp[n]까지 찾아준다.

 

 

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int dp[] = new int[n + 1];

		// bottom-up
		for (int i = 2; i <= n; i++) {
			dp[i] = dp[i - 1] + 1;
			
			if (i % 3 == 0)
				dp[i] = Math.min(dp[i], dp[i / 3] + 1);
			
			if (i % 2 == 0)
				dp[i] = Math.min(dp[i], dp[i / 2] + 1);
		}
		
		System.out.println(dp[n]);
	}

}