[伯俊]BOJ 1904 JAVA

5344 ワード
アルゴリズム#アルゴリズム# テキストリンク
BOJ 1904 01タイル

質問する


智媛にバイナリ数列を教えるために、智媛のお父さんはタイルをあげました.そして、これらのタイルはいずれも0か1と書かれたこまごましたタイルです.
ある日、やんちゃな東柱は志源の勉強を邪魔するために、0と書かれたこまごましたタイルを貼って、ペアの00タイルにしました.最終的には、現在1つの構成のタイルまたは2つの0タイルが接続されている1対の00タイルしか残っていません.
そのため、志源はタイルですべての大きさNのバイナリ数列を作ることができない.たとえば、N=1では1しか作成できませんが、N=2では00,11を作成できます.(01,10は作成できません.)また、n=4の場合、0011、0000、1001、1100、1111の計5個のバイナリ数列を作成することができる.
私たちの目標はNがタイミング智媛にできるすべての偽数を数えることです.タイルは無限に多いと仮定します.

入力


最初の行は自然数Nを与える.(1 ≤ N ≤ 1,000,000)

しゅつりょく


最初の行では、ソースが作成できる長さNのすべてのバイナリ数列の個数を15746で除算し、残りの数を出力します.

サンプルI/O


入力:4/出力:5

ソースコード

import java.util.Scanner;

public class Main {
    private static final int MAX = 1_000_001;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] arr = new int[MAX];

        arr[1] = 1;
        arr[2] = 2;

        for (int i = 3; i < MAX; i++) {
            arr[i] = (arr[i - 1] + arr[i - 2]) % 15746;
        }

        System.out.println(arr[n]);
    }
}

Comment


  • の簡単なルールを探してください.解答しやすい基礎dp問題
  • ヒント:n = 5の場合、00001 00100 00111 10000 10011 11100 10011 11001
    • テキストボックスのイベント適用(メールアドレス検証を含む)4-9
    [leetcode] 39. Combination Sum