[BOJ] 백준 11727번 - 2 x N 타일링 (2)

문제

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

11727번: 2×n 타일링 2

 

기존 문제

2021.12.14 - [Algorithm] - [BOJ] 11726 - 2 x n 타일링

[BOJ] 11726 - 2 x n 타일링

 

풀이

• 2 x N 크기의 직사각형을 2x1, 1x2, 2x2 크기의 타일로 채우는 방법의 수를 구하기 위해
  2 x 1 ~ 2 x N 크기 까지의 모든 직사각형에 대해 세 가지 타일로 채우는 방법의 수를 차례대로 구한다.
  => DP Bottom-Up 방식
• 점화식을 파악하기 위해 2x1 ~ 2x4 까지 예시를 그림으로 그려보면 아래와 같다.

• n번째 값 = (n-1번째 값 * 2) + n-2번째 값
• 2xN 타일링 (1) 문제에서 2열 짜리 공간에 대해 (1x2 타일 2개) or (2x2 타일 1개) 로 경우가 늘어났기 때문에
  n-2번째 값에 2를 곱해서 더해줘야 한다.
• 2 x n 크기의 직사각형을 2x1, 1x2 크기의 타일로 채우는 방법의 수
  = 2 x n-2 크기의 직사각형의 오른쪽에 1x2 크기의 타일을 2개 붙인 것 & 2x2 크기의 타일을 1개 붙인 것
  + 2 x n-1 크기의 직사각형의 오른쪽에 2x1 크기의 타일을 1개 붙인 것

 

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] dp = new int[n + 2];
        dp[1] = 1;
        dp[2] = 3;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
        }

        System.out.println(dp[n] % 10007);
    }
}

 

• 문제의 출력 조건은 '2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지' 이기 때문에 DP테이블의 N번째 값 % 10007 연산을 해줘야 하며, 3~N 까지의 연산 과정 매번 앞서 계산한 결과를 참조하기 때문에 DP 테이블의 모든 값들은 계산 과정에서 미리 % 10007 연산을 취해줘야 한다.

int[] dp = new int[n+1]; 으로 DP 테이블을 생성하면
입력 값 n이 1일 경우, int[] dp = new int[2]; 가 되어 dp[2]에서 index가 넘어가버려서 예외가 발생한다. 이를 방지하기 위해 여유공간으로 n+2 만큼의 크기로 생성하는 것.