[백준 JAVA] 11727 2xn 타일링 2

11727 2xn 타일링 2

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

문제설명

주어진 정수 n에 대해 2xN 크기의 타일을 1x2 또는 2x1 크기의 타일로 채우는 경우의 수를 계산한다.

접근방식

O(n)  시간복잡도

 

DP 배열은 상수 시간을 가진다.

 

문제 조건 분석 과정

 

dp[i]: 2xi 크기의 직사각형을 채우는 방법의 수를 저장한다.

dp[i] = dp[i-1] + 2 * dp[i-2]

• dp[i-1]은 마지막에 1x2 타일 하나를 수직으로 놓은 경우
• 2 * dp[i-2]는 마지막 두 열에 2x1 타일을 수평으로 놓은 경우와 두 개의 1x2 타일을 수평으로 놓은 경우이다.

 

전체코드

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

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

        int n = Integer.parseInt(br.readLine().trim());

        // 결과를 모듈로 나눈 나머지를 저장하기 위한 상수
        final int MOD = 10007;

        //dp[i]로 i 칸을 채우는 방법의 수를 저장
        int[] dp = new int[n + 1];

        // 기본 케이스: dp[0] = 1 (0 칸을 채우는 경우는 1가지) 및 dp[1] = 1 (1 칸을 채우는 경우는 1가지)
        dp[0] = 1;
        dp[1] = 1;

        // 동적 프로그래밍을 이용하여 dp 배열을 채움
        // i가 2부터 n까지 반복
        for (int i = 2; i <= n; i++) {
            // dp[i] = 두가지 경우의 수 고려
            // 1. (i-1)번째 칸을 채우고, 마지막에 1x2 타일을 추가하는 경우
            // 2. (i-2)번째 칸을 채우고, 마지막에 2x2 타일을 추가하는 경우 (2개가 필요함)
            dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % MOD;
        }

        //n 칸을 채우는 방법의 수 출력
        System.out.println(dp[n]);
    }
}