[BaekJoon]190401タイル(java)

5769 ワード
dynamic programming baekjoon アルゴリズムの問題を解く テキストリンク

🔗 質問リンク


https://www.acmicpc.net/problem/1904

📝 解題方法


この問題はNの増加による結果から導き出され解決される問題である.
問題のルールは以下の通りです.N番目に生成された数列は、N−1個の生成された数列に1を付加したときの数と、N−2個の生成された数列に00個のタイルを貼り付けたときの数である.
すなわち、arr[N]=arr[N]+arr[N]=arr[N−1]+arr[N−2]arr[N]=arr[N̈1]+arr[N̈2]である.

これを利用して,フィボナッチ問題のように動的プログラミングでコードを記述しようと試みた.

👨🏻‍💻 作成されたコード

import java.io.*;
public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int[] arr = new int[n+1];
		
		arr[1] = 1;
		if (n >= 2) arr[2] = 2;
		
		if (n >= 3) {
			for (int i=3; i<=n; i++) {
				arr[i] = (arr[i-1] + arr[i-2]) % 15746;
			}
		}
		
		System.out.println(arr[n]);
	}

}
実行コンテキスト
DevExpressでのレポートツールバーおよび表示状態設定