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

1. 문제설명

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

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

정수 N이 주어졌을 때, 위의 연산 세 개를 적절히 사용해서 1을 만들려고 한다.

연산을 사용하는 횟수의 최솟값을 구하는 문제이다.

• 시간 제한: 0.15초
• 메모리 제한: 128MB

 

2. 접근 방식

• `dp[i]`에 i를 1로 만드는데 필요한 소 연산 횟수를 저장한다.
• 점화식을 계산한다.
  • `dp[2]`, `dp[3]`은 각각 1로 초기화 한다.
  • `dp[i]`는 기본적으로 `dp[i-1] +1`로 초기화 한다. (1을 빼는 연산)
  • i가 2의 배수이면, `dp[i]`는 `dp[i/2] + 1`과 비교하여 더 작은 값을 선택한다.
  • i가 3의 배수이면, `dp[i]`는 `dp[i/3] + 1`과 비교하여 더 작은 값을 선택한다.

• 최종적으로 `dp[n]`을 구한다.

 

3. 틀린 이유

기존 방법

for(int i=4; i<=n; i++) {
    if(i%3 == 0) { // 3의 배수이면
        dp[i] = Math.min(dp[i-1], dp[i/3]) + 1;
        continue;
    }
    if(i%2 == 0) { // 2의 배수이면 (3의 배수이거나 아니거나)
        dp[i] = Math.min(dp[i-1], dp[i/2]) + 1;
        continue;
    }
    // 그 외
    dp[i] = dp[i-1] + 1;
}

3의 배수인 경우와 2의 배수인 경우, 각 조건에 대해 최소값을 계산하고 continue문을 사용해 다음 조건들을 건너뛰었다.

이 방법은 특정 조건에 해당하면 그 이후의 조건을 검사하지 않고 건너뛰기 때문에, 2의 배수이자 3의 배수인 경우에 대해서는 2로 나누는 최적의 경로를 고려하지 못한다.

예를 들어 i가 6일 때, 3의 배수인 경우를 먼저 처리하고 2의 배수로서의 가능성은 무시하게 된다.

 

4. 틀린 부분 수정

for(int i=4; i<=n; i++) {
    dp[i] = dp[i-1] + 1; // 1을 빼는 연산

    if(i%2 == 0) { // 2의 배수인 경우
        // 2로 나눈 경우와 비교하여 최솟값 선택
        dp[i] = Math.min(dp[i], dp[i/2] + 1);
    }

    if(i%3 == 0) { // 3의 배수인 경우
        // 3으로 나눈 경우와 비교하여 최솟값 선택
        dp[i] = Math.min(dp[i], dp[i/3] + 1);
    }
}

수정된 방법은 모든 경우를 고려하여, 최종적으로 최소 연산 횟수를 계산한다.

dp[i]는 1을 빼는 경우, 2로 나누는 경우, 3으로 나누는 경우 모두를 비교한 후 그 중 최솟값을 선택하게 된다. 모든 조건을 고려하여 최솟값을 갱신하기 때문에 최적의 결과를 구할 수 있다.

 

5. 최종 코드

import java.io.*;

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[2] = 1; dp[3] = 1; // 초기값 설정
        
        for(int i=4; i<=n; i++) {
            dp[i] = dp[i-1] + 1; // 1을 빼는 연산

            if(i%2 == 0) { // 2의 배수인 경우
                // 2로 나눈 경우와 비교하여 최솟값 선택
                dp[i] = Math.min(dp[i], dp[i/2] + 1);
            }

            if(i%3 == 0) { // 3의 배수인 경우
                // 3으로 나눈 경우와 비교하여 최솟값 선택
                dp[i] = Math.min(dp[i], dp[i/3] + 1);
            }

        }

        System.out.println(dp[n]);
    }
}