[Java] 11727번: 2xn 타일링 2 Silver 3

문제 링크

2xn 타일링 2가 있는 지 몰랐는데, 종이 붙이기 문제랑 완전히 똑같은 문제였다..

설명은 네이버 블로그에 잘 적혀있으니 바로 풀어보자!

점화식은 이렇게 구할 수 있다

x[n] = x[n-1] + 2*x[n-2]

그래서 코드는 점화식과 초기값만 바꾸면 된다.

정답

import java.io.*;
import java.util.*;

public class Main {
    private static int N;
    private static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 입력 받기
        N = Integer.parseInt(br.readLine());

        // dp
        if (N == 1) {
            System.out.println(1);
        } else if (N == 2) {
            System.out.println(3);
        } else {
            dp = new int[N + 1];
            dp[1] = 1;
            dp[2] = 3;
            for (int i = 3; i <= N; i++) {
                dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
            }

            System.out.println(dp[N]);
        }
    }
}