[백준] 11726 : 2×n 타일링

알고리즘 기초 1 / 2

DAY - 4

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

---

매일 BFS, DFS 처럼 그래프 탐색문제를 풀다가 DP를 푸니까 머리가 돌아가지 않았따,, DP에는 하향식, 상향식이 있는데 아직 상향식이 더 편하게 느껴져 상향식으로 문제를 풀어보았다. DP 문제들을 점차 풀어가면서 점화식을 만드는 능력을 길러야겠따,,,

package day1003;

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

public class Baekjoon_11726_2곱하기N타일링 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		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-1]+arr[i-2])%10007;
		}
		System.out.println(arr[N]%10007);
	}
}