[코딩테스트/백준 알고리즘] 11726번 : 2×n 타일링 (자바, Java 풀이)

문제

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

11726번: 2×n 타일링

---

문제 설명

---

문제 풀이

 2 X n 사각형의 제일 왼 쪽에 타일을 놓을 수 있는 방법은 두 가지가 있다. 이 두 경우를 고려해서 가로 폭을 2칸 줄인 2 X (n - 2)의 경우와, 가로 폭을 1칸 줄인 2 X (n - 1)의 경우로 나눠서 해결할 수 있다.

 따라서 memo[n] = memo[n - 1] + memo[n - 2]로 구할 수 있다.

 

 

예제)

 

 

---

코드

import java.util.*;

class Main{
    public static void main(String[] args) {
        int n = new Scanner(System.in).nextInt();
        int[] memo = new int[1001];
        memo[0] = 1;
        memo[1] = 1;
        for(int i = 2; i <= n; i++) {
            memo[i] = memo[i - 2] + memo[i - 1];
            memo[i] %= 10007;
        }
        System.out.println(memo[n]);
    }
}