[백준] 11726번 - 2*n 타일링

 

 

머리로만 풀다보니 제대로 안풀렸는데 그림으로 그리니 간단하게 해결이 되었다.

이렇게 1일 때는 1, 2일 때는 2, 3일 때 3, 4일 때 5, 5일 때 8.... 이 규칙성을 보면 n이 3보다 클 때 n으로 만들 수 있는 조합의 수는 f(n)=f(n-1) + f(n-2)라는 식을 세울 수 있다. 이 식을 이용하여 문제를 해결하면 된다.

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

public class p11726 {
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int a = Integer.parseInt(br.readLine());
		int[] ary = new int[a + 2];
		ary[1] = 1;
		ary[2] = 2;
		for (int i = 3; i <= a; i++) {
			ary[i] = (ary[i - 1] + ary[i - 2]) % 10007;
		}
		System.out.println(ary[a]);
	}
}