[BOJ] 1463 - 1로 만들기 Java 풀이

풀이

문제 링크는 아래에 있다.

BOJ 1463 - 1로 만들기

처음 문제를 풀이할 때는 다음과 같이 생각했다.

이 문제는 다이나믹 프로그래밍의 전형적인 문제이다.
우선 하나의 문제를 푸는 방법이 그 전에 풀었던 문제의 결과를 사용하게 된다.
그리고 그렇기 때문에 전에 풀었던 문제의 결과를 저장해두고 재사용 할 수 있다.

문제에서 제시되는 경우의 수는 총 세가지가 있다.

1. 1을 빼는 경우
2. 2로 나누는 경우
3. 3으로 나누는 경우

예를 들어 12를 1로 만드는 방법을 생각하면 우리는 다음과 같이 생각할 수 있다.

1. 11을 만드는 방법의 수에서 1을 더하는 방법
2. 6을 만드는 방법의 수에서 1을 더하는 방법
3. 4를 만드는 방법의 수에서 1을 더하는 방법

이 중에서 가장 작은 방법의 수가 12를 1로 만드는 방법의 수이다.

그러므로 우리가 n을 1로 만드는 방법의 수를 구한 문제의 답을 memoization[n]에 저장한다고 가정하면, 문제는 다음과 같이 쓸 수 있다.

memoization[n] = (memoization[n - 1], memoization[n / 2], memoization[n / 3] 중의 최솟값)

물론, n이 2로 나누어 떨어지는지, 3으로 나누어 떨어지는지 까지도 판별을 하면서 답을 구해야 한다.

구현

코드 구현은 다음과 같다.

import java.util.Scanner;

class Solution_1463 {
    private final int MAX_SIZE = 1000000 + 1;
    private final int input;
    private final int[] memoization;

    Solution_1463(int input) {
        this.input = input;
        memoization = new int[MAX_SIZE];
        memoization[2] = 1;
        memoization[3] = 1;
    }

    private int calculateMemoization(int num) {
        for(int i = 4; i <= num; i++) {
                memoization[i] = memoization[i - 1] + 1;
                if(i % 2 == 0) {
                    memoization[i] = Math.min(memoization[i], memoization[i / 2] + 1);
                }
                if(i % 3 == 0) {
                    memoization[i] = Math.min(memoization[i], memoization[i / 3] + 1);
                }
        }
        return memoization[num];
    }

    public int getAnswer() {
        return calculateMemoization(input);
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int input = scanner.nextInt();
        System.out.print(new Solution_1463(input).getAnswer());
    }
}

코드의 구현을 살펴보면, 기본적으로 Main 클래스의 Main 함수에서는 입출력을 담당한다.
사용자 입력을 받고, 입력을 Solution 클래스에 넘겨주어 초기화를 시키고 답을 구하게 한다.
구한 답을 표준 입출력 함수를 이용하여 출력시킨다.

Solution 클래스에서는 memoization 배열과 최대 크기, 그리고 받을 입력을 저장할 필드를 선언한다.
이후 생성자에서 데이터를 초기화한다.

getAnswer() 메서드는 해당하는 calculateMemoization() 메서드를 호출해 구한 답을 리턴시킨다.

calculateMemoization() 메서드는 memoization 배열의 값들을 아래부터 반복하면서 계산한다.
처음에는 memoization[n]에 memoization[n - 1] + 1의 값을 할당을 한다.
그 후에 2로 나누어 질 때는 memoization[n / 2]와 비교 후 최솟값을 할당하고,
3으로 나누어 질 떄는 memoization[n / 3]과 비교 해 최종 최솟값을 구한다.

그 후에 최종적으로 momoization[n]값을 리턴 시켰다.

풀이 결과

처음에 런타임 에러는 인텔리 제이에서 문제를 푸는데 Main클래스를 다른 클래스로 변경해서 생기는 오류였다.