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

문제

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

11727번: 2×n 타일링 2

---

문제 설명

---

문제 풀이

문제에 대한 전반적인 설명은 아래 글을 참고하세요.

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

 

 이 문제에서는 2 X 2 타일이 생겼기 때문에 맨 왼쪽에 2칸짜리 타일을 채우는 경우가 2개가 나온다. 

 따라서 memo[n] = memo[n - 1] + (2 X 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;
        memo[2] = 3;

        for(int i = 3; i <= n; i++) {
            memo[i] = memo[i - 1] + (memo[i - 2] * 2);
            memo[i] %= 10007;
        }
        System.out.println(memo[n]);
    }
}