[P&B] #104 BAEKJOON 1463

백준 1463번 1로 만들기 JAVA

문제 설명

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

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입력

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

 

출력

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

 

나의 문제 풀이 코드

import java.io.*;

public class bj1463 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N + 1]; // dp[i]는 i를 1로 만드는데 필요한 최소 연산 횟수를 저장

        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + 1; // 현재 수에서 1을 뺀 경우
            if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1); // 현재 수를 2로 나눈 경우
            if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1); // 현재 수를 3으로 나눈 경우
        }

        bw.write(String.valueOf(dp[N]));
        bw.close();
    }
}

 

문제 풀이 코멘트

주어진 문제는 동적 계획법(Dynamic Programming)을 사용하여 풀 수 있습니다. 

• 주어진 수 N에 대해, N-1, N/2, N/3 세 가지 경우 중에서 가장 적은 횟수로 1을 만들 수 있는 경우를 선택합니다.
• 이전에 계산한 결과를 활용하여 중복 계산을 피합니다.

사실 동적 계획법에 대해 잘 몰라서 동적 계획법 부터 알아보았습니다.

동적 계획법(Dynamic Programming, DP)은 많은 문제를 해결하는 데 사용되는 알고리즘 설계 기법 중 하나입니다. 주로 중복된 계산을 피하고 최적화된 해결 방법을 찾는 데 사용됩니다. DP는 다음과 같은 특징을 가집니다:

1. 중복 계산을 피한다: DP는 중복되는 계산을 피하고, 이전 계산 결과를 저장하고 재사용하여 계산 효율성을 높입니다. 이로 인해 많은 경우에 지수 시간 복잡도를 다항 시간 복잡도로 줄일 수 있습니다.

2. 문제를 작은 하위 문제로 분할: DP는 큰 문제를 작은 하위 문제로 나누어 해결합니다. 이러한 하위 문제들은 서로 독립적이며 전체 문제의 해결에 도움을 줍니다.

3. 점화식으로 문제 해결: DP는 점화식(Recurrence Relation)을 사용하여 문제를 해결합니다. 이전 단계의 해결 결과를 기반으로 현재 단계의 해결 결과를 계산합니다.

 

동적 계획법을 사용하는 일반적인 단계는 다음과 같습니다:

1. 문제 정의: 주어진 문제를 정확하게 정의하고 어떤 하위 문제로 나눌 수 있는지 고민합니다.

2. 점화식 정의: 각 하위 문제의 해결을 위한 점화식(Recurrence Relation)을 정의합니다. 이전 단계의 해결 결과를 활용하여 현재 단계의 해결 결과를 계산합니다.

3. 초기 조건 설정: 가장 작은 하위 문제에 대한 초기 조건을 설정합니다. 이 초기 조건은 점화식에서 시작점 역할을 합니다.

4. 상향식 계산: 작은 하위 문제부터 시작하여 큰 문제를 해결하기 위해 상향식으로 계산합니다. 이전 단계의 계산 결과를 활용하여 다음 단계의 계산을 수행합니다.

5. 해 결정과 저장: 계산된 결과를 저장하고 필요한 경우 재사용합니다. 이로써 중복 계산을 피합니다.

6. 최종 해 도출: 큰 문제의 해결 결과를 얻습니다.

 

이 문제에서는 주어진 수 N을 1로 만들기 위해 가능한 세 가지 연산을 사용할 수 있으며, 각 숫자마다 최소 연산 횟수를 저장해가면서 문제를 푼다는 아이디어를 사용합니다.

• int[] dp = new int[N + 1];: dp 배열을 선언하며, dp[i]는 숫자 i를 1로 만들기 위한 최소 연산 횟수를 저장합니다. 배열의 크기는 N+1로 설정하고, 0부터 N까지의 모든 숫자에 대한 최소 연산 횟수를 저장하기 위해 N+1 크기로 설정합니다.
• for (int i = 2; i <= N; i++) {: i는 2부터 N까지 반복합니다. 왜냐하면 1은 이미 1로 만들어진 수이기 때문에 dp[1]의 값을 미리 설정해주었고, 2부터 N까지의 숫자에 대한 최소 연산 횟수를 구해야 하기 때문입니다.
• dp[i] = dp[i - 1] + 1;: 현재 숫자 i를 1로 만들기 위해, 이전 숫자인 i-1에서 1을 빼고 1을 더하는 연산을 한 번 더 수행해야 합니다. 따라서 dp[i]를 dp[i-1] + 1로 갱신합니다.
• if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);: 현재 숫자 i가 2로 나누어 떨어지는 경우, i를 2로 나누어서 얻는 최소 연산 횟수는 dp[i/2] + 1입니다. 이 값을 dp[i]와 비교하여 최솟값을 선택합니다.
• if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);: 현재 숫자 i가 3으로 나누어 떨어지는 경우, i를 3으로 나누어서 얻는 최소 연산 횟수는 dp[i/3] + 1입니다. 이 값을 dp[i]와 비교하여 최솟값을 선택합니다.

 

위의 과정을 반복하면, dp[N]에는 숫자 N을 1로 만들기 위한 최소 연산 횟수가 저장됩니다. 이 값을 출력하면 문제의 답이 됩니다.

 

예를 들어, N이 6일 경우 다음과 같이 각 숫자에 대한 최소 연산 횟수가 계산됩니다:
dp[2] = dp[1] + 1 = 1 + 1 = 2
dp[3] = dp[2] + 1 = 2 + 1 = 3
dp[4] = dp[2] + 1 = 2 + 1 = 3
dp[5] = dp[4] + 1 = 3 + 1 = 4
dp[6] = dp[3] + 1 = 3 + 1 = 4
따라서, dp[6]에는 숫자 6을 1로 만들기 위한 최소 연산 횟수인 4가 저장되며, 이 값이 출력됩니다.

 

이제 문제 이외의 몇 가지 예제를 통해 DP를 이해해 보겠습니다:

예제 1: 피보나치 수열

피보나치 수열은 다음과 같은 점화식을 가집니다: F(n) = F(n-1) + F(n-2) (단, F(0) = 0, F(1) = 1).

이를 DP로 해결하면:

public int fibonacci(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

예제 2: 배낭 문제 (Knapsack Problem)

배낭 문제는 다양한 버전이 있으나, 0/1 배낭 문제를 예로 들어보겠습니다. 주어진 가방의 최대 무게를 초과하지 않는 가치의 최대 합을 구하는 문제입니다. 각 물건은 무게와 가치를 가지고 있으며, 한 번에 하나의 물건만 선택할 수 있습니다.

이 문제를 DP로 해결하면:

public int knapsack(int[] weights, int[] values, int maxWeight) {
    int n = weights.length;
    int[][] dp = new int[n + 1][maxWeight + 1];
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= maxWeight; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    
    return dp[n][maxWeight];
}

동적 계획법은 이와 같이 다양한 문제에 적용될 수 있으며, 문제를 작은 하위 문제로 분할하고 이전 계산 결과를 활용하여 최적의 해를 찾는 데 사용됩니다. 이를 통해 효율적으로 다양한 문제를 해결할 수 있습니다.