[BOJ]1726-2 xnタイルJavaプール

に答える

問題リンクは下にあります.
BOJ 11726-2 xnタイル
考え方を少し違うように考えるべきだと思います.
自分一人で遊んでいて特定の場所で塞がれていたので一目見ました.
最初に思いついた答えは以下の通りです.
この問題はダイナミックプログラミングで解決できると思います.
横方向の長さnのタイルは、n−1のタイルに縦方向のタイルを貼り付けるか、n−2のタイルに横方向のタイルを2つ貼り付けるからである.
すなわち,以前に解いた問題の一部を再解答しなければならない結果は,注釈を新しい方法として保存し,それを書き出して書くことで効率を向上させることができる.
これらの問題は典型的な動的プログラミング問題の特徴と見なすことができる.
また,これはTMIであり,動的プログラミング問題を解く際にGRADYアルゴリズムを用いる場合がある.
まだ正確な理由が分からないので、知ってから整理したいです.
いずれにしても、問題を解く過程はそう思っています.
最初はタイルの長さ1とタイルの長さ2から考えていました.
そしてタイルの長さが3の場合を考えて、1から3の場合、3個立てて作る場合は2回出ます.
つまり、この部分に対する考え方が一致しなかったため、問題を解決できなかったということです.
参考になるその他の回答は以下の通りです.
2*n長さのタイルを作る方法は以下の通りです.

n長さのタイルは、n−1タイルに縦タイルを1つ貼り付けることができる.

(1ケース)

n長さのタイルは、n−2タイルに2つの横タイルを貼ることができる.

(1ケース)
したがって、n長さのタイルのタイル総数をmemorization[n]と呼ぶと、式は次のように作成できます.

memoization[n] = memoization[n - 1] + memoization[n - 2]

これにより,n長タイル中のタイルの総数を求めることができる.

インプリメンテーション

import java.util.Scanner;

class Solution_11726 {
    private final int MAX_NUM = 1001;
    private final int input;
    private final long[] memoization;
    Solution_11726(int input) {
        this.input = input;
        memoization = new long[MAX_NUM];
        memoization[1] = 1;
        memoization[2] = 2;
    }

    public long getAnswer() {
        for(int i = 3; i <= input; i++) {
                memoization[i] = (memoization[i - 2] % 10007 + memoization[i-1] % 10007) % 10007;
        }
        return memoization[input];
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution_11726(new Scanner(System.in).nextInt()).getAnswer() % 10007);
    }
}

コード構造は次のとおりです.
Main関数に1行書こうと思っていたので、そのように書きましたが、変数別に書いた方が見やすいようです.
つまり,MainクラスのMain関数は入力と出力のみを担当し,すべての演算をSolutionに委任する.
ソリューションクラスの構造は次のとおりです.
入力したフィールドと配列の最大サイズを定義し、問題の結果を記録するアノテーション配列を作成します.
ソリューションクラスの作成者は、入力を受信してレイアウトを初期化します.
答えはgetAnswer()で演算されます.
getAnswer()は、入力コメントの配列の一部の問題をfor文で解決し始めます.
基本フレームワークは上に書いた備考[n]=備考[n-1]+備考[n-2]である.
しかし問題では,対応する値を10007で割って余りを求めることが求められているため,上記の形式となっている.
問題の答えがint範囲の最大値21億を超えたためか,問題にはこのように答えが与えられた.
残数を求める方法は少し特殊で、(a+b)%c=(a%c+b%c)%cと同じです.
これは後で単独で証明されるかもしれませんが、まず、対応する方法をよく使うので、暗記することをお勧めします.
これにより、getAnswer()はmemorization[input]値を返します.

回答結果