[백준 온라인 저지] 1904. 01타일

2종류의 타일이 있다. 하나는 1이 쓰인 타일이고, 다른 하나는 00이 쓰인 타일이다.

지원이는 이 타일로 길이가 N인 2진 수열을 만들려고 한다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

 

1. 입력

- 첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

 

2. 출력

- 첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

 

3. 예제

 

4. 코드

import java.util.*;
class Main {
    public static void main(String[] args){
        int n = new Scanner(System.in).nextInt();
        if(n==1) System.out.print(1);
        else if(n==2) System.out.print(2);
        else{
            int[] d = new int[n+1];
            d[1] = 1; d[2] = 2;
            for(int i=3 ; i<=n ; i++)
                d[i] = (d[i-1] + d[i-2])%15746;
            System.out.print(d[n]);
        }
     }
}

- 21640KB, 224ms