[BOJ] 백준 11726번 - 2 x n 타일링

문제

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

11726번: 2×n 타일링

 

풀이

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

• n번째 값은 앞서 계산한 n-1번째 값과 n-2번째 값을 더한 결과이다.
• 2 x n 크기의 직사각형을 2x1, 1x2 크기의 타일로 채우는 방법의 수
  = 2 x n-2 크기의 직사각형의 오른쪽에 1x2 크기의 타일을 2개 붙인 것
  + 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] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;    // 다음 연산 값을 제대로 계산하기 위해 매번 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 만큼의 크기로 생성하는 것.