[BOJ] 11726 - 2xn 타일링

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제 설명

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

난이도: 실버 3

사용 언어: JAVA

 

문제는 간단합니다. 2xn 크기의 직사각형을 1x2, 2x1 크기의 타일로 채우는 방법의 수를 구하면 되고, 아래의 그림은 2x5 크기의 직사각형을 채운 한 가지 방법의 예시입니다.

 

입력 값으로는 n이 주어지며, 2xn 크기의 직사각형을 채우는 방법의 수를 10.007로 나눈 나머지를 출력하면 됩니다.

 

풀이

이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 우선 기본적인 아이디어는 n까지의 타일을 채우는 경우의 수는, 이미 만들어진 n-1개의 타일 뒤에 2x1 크기의 타일을 붙이는 경우의 수와, 또 이미 만들어진 n-2개의 타일 뒤에 1x2 크기의 타일을 두 개 추가하는 경우의 수, 둘 뿐이라는 것입니다. 아래의 그림을 살펴보겠습니다.

 

진하게 표시된 마지막에 붙이는 타일을 제외하고는 이미 최대 값을 구해두었다고 가정하면, n까지의 타일을 채우는 경우의 수는 n-1까지의 타일을 채우는 경우의 수와 n-2까지의 타일을 채우는 경우의 수를 합한 값이 됩니다.

 

이 아이디어를 가지고, 1부터 n까지의 배열을 생성해주면 됩니다.

 

import java.util.Scanner;
 
class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n;
        n = sc.nextInt();
        int []arr = new int[n+1]; //편의상 0을 제외한 1부터 n까지의 배열을 만들기 위해 n+1 크기의 배열을 선언했습니다.
        int i;
        arr[0] = 1; // 실제로는 존재하지 않지만 arr[2]를 만들기 위한 값입니다.
        arr[1] = 1; // 2x1 크기를 채울 수 있는 경우의 수는 1개 뿐이겠죠?
 
        for(i=2;i<=n;i++){ // 2부터 n까지 배열을 위에서 설명한 방법으로 채워나갑니다.
            arr[i] = (arr[i-1] % 10007) + (arr[i-2] % 10007);
        }
 
        System.out.println(arr[n]%10007);
    }
}
 

 

문제의 답을 10007로 나눈 나머지를 출력하라고 한 것은, n의 범위가 1000까지여서, 분명 중간에 경우의 수가 int의 범위를 넘는 굉장히 큰 수 까지 치솟을 것이기 때문입니다. 그래서 마지막에만 arr[n]을 10007로 나눈 값을 정답으로 출력하면, 중간에 반복문에서 이미 int의 범위를 넘어서서, 잘못된 답이 도출될 수 있습니다.

 

따라서 반복문에서 계속 10007로 나눈 나머지 값을 넣어줌으로써, int의 범위를 초과하는 것을 방지할 수 있습니다.

 

그리고 많이들 하시는 실수로 arr[2] = 2를 반복문 전에 그냥 적어주시는 경우가 있는데, 이런 경우에는 입력 값인 n으로 1이 들어오면 배열의 크기를 초과하는 인덱스를 갖기 때문에, if문을 통해 예외 처리를 해 주거나하는 방법을 사용하셔야 에러가 나지 않습니다.