[백준 1904] 01타일 (Java)

n=1 : 1

n=2 : 00 / 11

n=3 : 001 / 100 / 111

n=4 : 0000 / 0011 / 1100 / 1001 / 1111

n=5 : 00001 / 00100 / 10000 / 00111 / 10011 / 11001 / 11100 / 11111

...

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
 
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n+2];
        Arrays.fill(arr, 987654321);
 
        arr[1]=1;
        arr[2]=2;
        if(n>=3){
            for(int i=3; i<=n; i++){
                arr[i]=arr[i-1]+arr[i-2];
                arr[i]%=15746;
            }
        }
 
        System.out.println(arr[n]);
 
    }
}