[백준] 1463번 : 1로 만들기 – JAVA [자바]

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

1463번: 1로 만들기

 

---

• 문제

 

 

---

• 문제 풀이

백준 1463번 1로 만들기는 실버 3 난이도의 DP 문제이다. 이 문제는 DP 문제 중에서도 기본적인 문제이니 꼭 풀어보고 이해하는 것을 추천한다. 이 문제에서는 정수 N이 주어지고 이 정수를 1로 만들 때 사용되는 최소 연산 횟수를 구하면 된다.

 

할 수 있는 연산은 3가지가 있다.

1. N을 3으로 나눌 수 있으면 3으로 나눈다.

2. N을 2로 나눌 수 있으면 2로 나눈다.

3. N에서 1을 뺀다.

 

이 문제는 4가지의 케이스로 나눠서 풀 수 있다. 그전에 배열 dp를 선언하는데 dp [i]는 1로 만드는데 드는 최소 연산 횟수라고 정의하겠다.

 

Case 1 : N % 6 == 0 (6으로 나눠지는 경우)

만약에 N이 6으로 나눠지는 경우면 3으로 나눠지는 경우, 2로 나눠지는 경우, 그리고 1을 뺀 경우 모두를 살펴봐야 한다. 따라서 다음과 같이 공식을 쓸 수 있다.

 

dp [n] = Math.min (dp [n % 3], Math.min(dp [n % 2], dp [n - 1]) + 1

 

 

Case 2 : N % 3 == 0 (3으로만 나눠지는 경우)

만약에 N이 3으로만 나눠지면 (2로는 나누어지지 않는다) 3으로 나눠지는 경우 그리고 1을 뺀 경우, 총 2가지를 고려해야 한다. 따라서 다음과 같이 공식을 쓸 수 있다.

 

dp [n] = Math.min (dp [n % 3], dp [n - 1]) + 1

 

 

Case 3 : N % 2 == 0 (2로만 나눠지는 경우)

N이 3로만 나눠지면 2로 나눠지는 경우 그리고 1을 뺀 경우를 고려해야 한다.

 

dp [n] = Math.min (dp [n % 2], dp [n - 1]) + 1

 

 

Case 4 : N % 3 != 0 && N % 2 != 0 (2, 3으로 나눠지지 않는 경우)

나눠지지 않으면 1만 뺀 경우에서 1을 더해준다.

 

dp [n] = dp [n - 1] + 1

 

 

이렇게 해서 총 4가지의 경우를 살펴봤다. 모든 경우에서 1을 더해주는 이유는 3으로 나눴을 때, 혹은 2로 나눴을 때, 혹은 1을 뺀 경우로 가는데 한 번의 연산이 필요하기 때문이다.

 

 

---

• 코드

 

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[1000001];  //DP 배열 초기화
        dp[2] = 1;
        dp[3] = 1;
        for (int i = 4; i <= n; i++) {
            if (i % 6 == 0) {
                //6으로 나눠지면 3으로 나눠지는 경우, 2로 나눠지는 경우 둘다 확인
                dp[i] = Math.min(dp[i/3], Math.min(dp[i/2], dp[i-1])) + 1;
            } else if (i % 3 == 0) {
                //3으로 나눠지는 경우
                dp[i] = Math.min(dp[i/3], dp[i-1])+1;
            } else if (i % 2 == 0) {
                //2로 나눠지는 경우
                dp[i] = Math.min(dp[i/2], dp[i-1]) + 1;
            } else {
                //나눠지지 않는 경우
                dp[i] = dp[i-1] + 1;
            }
        }
        System.out.print(dp[n]);
    }
}