[백준/JAVA] 14852번 타일 채우기 3

• https://www.acmicpc.net/problem/14852

1. 문제

2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자.

2. 문제 접근

1) 첫째 줄에 길이 N을 입력받는다.
2) 타일 채우기의 규칙을 파악한다.
2-1) N이 1일 때 경우의 수는 2, N이 2일 때 경우의 수는 7이다.
2-2) N이 3이상일 때 N-1 크기에서 채우는 경우의 수는 2가지이다.
2-3) N-2 크기에서는 채우는 경우의 수는 3가지이다.
2-4) N-(3이상) 크기에서는 채우는 경우의 수는 2가지이다.
3) 재귀적으로 표현시 시간초과가 발생하기 때문에 모든 타일 채우는 경우의 수 배열의 2배를 더한 값을 저장하고 N번 째 경우의 수는 2배를 더한 값 + N-2의 경우의 수로 표현한다.

3. 코드

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

public class Main {
    static long tile[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        tile = new long[N+1];
        tile[0] = 1;
        tile[1] = 2;
        if(N>1)
            tile[2] = 7;
        long temp =20;
        for(int i=3;i<=N;i++) {
            tile[i] = (temp + tile[i-2]) % 1000000007;
            temp = (temp + tile[i]*2) % 1000000007;
        }
        System.out.println(tile[N]);
    }
}