[백준] 1904 01타일

문제 출처: www.acmicpc.net/problem/1904

1904번: 01타일

: 00으로 이루어진 타일과 1로 이루어진 타일로 만들 수 있는 길이 N 타일의 가지 수를 구해야 한다.

: 우선 N이 1인 경우는 1로 밖에 만들 수 없기 때문에 1이고, N이 2인 경우는 00과 11이 존재하므로 2가 된다.

: N이 3이상인 경우 N-1길이의 타일에 1을 붙여서 만드는 경우와 N-2 길이의 타일에 00을 붙여서 만드는 경우로 나누어 생각해 볼 수 있다.

: N-2에 11을 붙이는 경우는 N-1에 1을 붙이는 경우에서 중복될 수 있기 때문에 고려하지 않는다.

: 따라서 [N번째 타일의 가지수] = [N-1의 가지수] + [N-2의 가지수]가 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		int N = Integer.parseInt(br.readLine());
		
		int[] arr = new int[N+2];
		arr[1] = 1;
		arr[2] = 2;
		for(int i = 3; i <= N; i++) {
			arr[i] = (arr[i-2] + arr[i-1])%15746;
		}
		System.out.println(arr[N]);
	}
}