[BOJ]1463-1 Javaプールの作成

に答える

問題リンクは下にあります.
使BOJ 1463-1
初めて問題を解いたとき、私は次のように思いました.
この問題はダイナミックプログラミングの典型的な問題である.
まず、1つの解題方法は、前の解題の結果を使用します.
また、これまでに解いた問題の結果を保存して再利用することができます.
問題で提起された状況の総数は3種類ある.

1から

を減算

2

3;

たとえば、12を1にする方法を考えてみましょう.

11のメソッド数に1を加算するメソッド

を作成する

6のメソッド数に1を加算するメソッド

を作成する

4のメソッド数に1を加算するメソッド

を作成する
このうち最小のメソッド数は12を1にするメソッド数である.
したがって,nを1とする方法の個数を求める問題の答えをmemorization[n]に格納すると仮定すると,問題は次のように書くことができる.

memoalization[n]=(memoalization[n-1]、memoalization[n/2]、memoalization[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関数がI/Oを担当する.
ユーザー入力を受信し、入力をソリューションクラスに渡し、初期化して答えを得る.
求めた答えを標準I/O関数で出力します.
「ソリューション」クラスでは、注釈シナリオ、最大サイズ、および入力を保存するフィールドが宣言されます.
次に、ジェネレータでデータを初期化します.
getAnswer()メソッドは、対応するcalculateMemoization()メソッドを呼び出して、求めた答えを返します.
calculateMemoization()メソッドは、以下からmemoization配列の値を繰り返し計算します.
最初にmemorization[n]にmemorization[n-1]+1の値を割り当てます.
そして、2に分割されると、「備考[n/2]」と比較した最高値が指定される.
3に分けた場合,備忘録[n/3]と比較して最終的な最高値を求める.
そして最終的にmooization[n]値を返します.

回答結果

最初は、Mainクラスを別のクラスに変更したため、ランタイムエラーが発生しました.