[코테] 백준 1463

내가 왜 이렇게 문제를 풀었는지

문제 분석

이 문제는 주어진 정수 N을 1로 만들기 위해 필요한 최소 연산 횟수를 구하는 것입니다. 사용할 수 있는 연산은 다음 세 가지입니다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

접근 방식

이 문제는 각 단계에서 최적의 선택을 해야 하는 전형적인 동적 계획법(Dynamic Programming, DP) 문제입니다. 따라서, DP 배열을 사용하여 N까지의 모든 수에 대해 1로 만드는 최소 연산 횟수를 기록했습니다. 바텀업(Bottom-up) 방식으로 접근하여, 작은 문제부터 해결하면서 점점 큰 문제로 확장해 나갔습니다.

코드 설명

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

import static java.lang.Math.min;

public class P1463 {
    private static int solution(int n){
        int[] dp = new int[1000001];

        dp[1] = 0;  // 1은 이미 1이므로 연산 필요 없음
        dp[2] = 1;  // 2는 한 번 나누기 2 연산으로 1이 됨

        for(int i = 3; i < 1000001; i++){
            int cnt1 = Integer.MAX_VALUE;
            int cnt2 = Integer.MAX_VALUE;
            int cnt3 = 0;

            if (i % 3 == 0){
                cnt1 = 1 + dp[i/3];
            }

            if (i % 2 == 0){
                cnt2 = 1 + dp[i/2];
            }

            cnt3 = 1 + dp[i-1];

            dp[i] = min(min(cnt1, cnt2), cnt3);
        }
        return dp[n];
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        System.out.println(solution(N));
    }
}

이러한 문제의 특성

동적 계획법 (DP)의 특징

이 문제는 동적 계획법의 전형적인 예입니다. DP는 복잡한 문제를 더 간단한 하위 문제로 나누어 해결하는 방법입니다. 이 문제에서는 각 숫자를 1로 만드는 과정을 하위 문제로 나누어, 각 단계에서 최적의 선택을 기록하고, 이를 바탕으로 전체 문제를 해결합니다.

바텀업 방식

바텀업 방식은 작은 문제부터 해결하여 점점 큰 문제로 확장해 나가는 접근 방식입니다. 이 문제에서는 숫자 1부터 시작하여 주어진 숫자 N까지의 모든 숫자를 1로 만드는 최소 연산 횟수를 차례로 계산합니다. 이렇게 하면, 이미 계산된 결과를 재사용할 수 있어 효율적입니다.

메모이제이션

메모이제이션은 이미 계산된 값을 저장하여 동일한 계산을 반복하지 않도록 하는 기법입니다. 이 문제에서는 dp 배열이 메모이제이션을 담당합니다. 각 숫자를 1로 만드는 최소 연산 횟수를 dp 배열에 저장하고, 이를 이용하여 다음 숫자의 최소 연산 횟수를 계산합니다.