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

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

1463번: 1로 만들기

 

---

💭 문제

 

 

 

---

💬 풀이

Bottom-Up 방식으로 반복문을 이용해서 풀었습니다.

먼저 가능한 연산은 1) 3으로 나누기, 2) 2로 나누기, 3) 1을 빼기 3가지 경우로, 이 문제는 3가지 연산을 이용해서 N을 1로 만들 수 있는 최소한의 연산 횟수를 구하는 문제입니다.

 

여기서 주의해야 할 점은 단순히 큰 수로 연산하는 것이 최소 연산 횟수를 구할 수 있는 것은 아니라는 점입니다.

예를 들어 10의 경우, 연산 가능한 큰 수로 연산하면 10 -> 5(2로 나눔) -> 4(1을 뺌) -> 2(2로 나눔) -> 1(2로 나눔) 로 4번의 연산을 합니다. 하지만 실제 최소 연산 횟수는 10 -> 9(1을 뺌) -> 3(3으로 나눔) -> 1(3으로 나눔) 로 3번이 정답입니다.

 

일단 dp 테이블에는 i를 1로 만들기 위해 필요한 최소 연산 횟수가 들어갑니다. dp[1] = 0, dp[2] = 1, dp[3] = 1, ... 등이 될 것입니다. 

 

i를 연산한다고 할 때, 가능한 경우는 i/3, i/2, i-1 가 있을 것입니다. 따라서 i를 1로 만들기 위해 필요한 최소 연산 횟수, 즉 dp[i]는 dp[i/3], dp[i/2], dp[i-1] 세 가지 중 최소인 경우에 현재 연산 횟수인 1번을 더한 값이 될 것입니다.

이를 점화식으로 나타내면 dp[i] = min(dp[i/3], dp[i/2], dp[i-1]) + 1 가 됩니다.

따라서 2부터 N까지의 dp 테이블을 차례대로 구하고 dp[N]을 출력하면 N을 1로 만들 수 있는 최소한의 연산 횟수를 구할 수 있을 것입니다.

 

단, 주의할 점은 dp[i/3]은 i가 3으로 나눠 떨어질 때, dp[i/2]는 i가 2로 나눠 떨어질 때만 가능한 연산이기 때문에 조건을 붙여줘야 합니다.

 

 

✔ 소스코드

• N은 최대 10⁶ 까지 나올 수 있기 때문에 dp 테이블의 크기는 1000001로 설정합니다. (0 ~ 1000000)
• 먼저, 1을 빼는 경우로 초기화를 한 뒤, 3으로 나누는 연산이 가능하고 그 경우가 더 작다면 dp[i/3] + 1로 바꿉니다. 만약 3으로 나누어 떨어지지 않는다면 다음 if 문으로 넘어갑니다. 
• 다음, 2로 나누는 연산이 가능하고 그 경우가 더 작다면 dp[i/2] + 1로 바꿉니다. 이렇게 해서 3가지 연산 중 최적의 경우를 구할 수 있게 됩니다.

import java.io.*;

public class BJ1463 {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		// N <= 1000000
		int[] dp = new int[1000001];
		
		for(int i=2; i<=N; i++) {
			// 1을 빼는 연산
			dp[i] = dp[i-1] + 1;
			
			// 3으로 나눠떨어진다면
			if(i % 3 == 0) {
				// 3으로 나눴을 때의 경우가 더 최적이라면 그것으로 교체
				dp[i] = Math.min(dp[i], dp[i / 3] + 1);
			}
            
			// 2로 나눠떨어진다면
			if(i % 2 == 0) {
				// 2로 나눴을 때의 경우가 더 최적이라면 그것으로 교체
				dp[i] = Math.min(dp[i], dp[i / 2] + 1);
			}
		}
		
		System.out.println(dp[N]);
	}

}