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

に答える

問題リンクは下にあります.
BOJ 11727-2 xnタイル2
117262 xnタイルの問題では、これは小さな変化です.
まず11726の解答用紙を見ることをお勧めします.
解題は以下の通りです.
2*n長さのタイルを作る方法は以下の通りです.

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

(1ケース)

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

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

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

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

インプリメンテーション

import java.util.Scanner;

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

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

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

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

回答結果