[JAVA] 백준 11726번: 2xn 타일링

 

---

문제

• 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 출력하는 문제.

 

아이디어

• 각 사이즈의 직사각형을 채울 수 있는 방법의 수 간 규칙성을 찾는다.

경우의 수를 직접 따져본 그림

• 방법의 수는 각각 1, 2, 3, 5, ... 순으로 증가한다.
• 이를 점화식으로 표현하면 다음과 같다.

$$a_{n} = a_{n-1} + a_{n-2}$$

 

풀이

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

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

        int[] arr = new int[1001];
        int n = Integer.parseInt(br.readLine());

        arr[1] = 1;
        arr[2] = 2;
        // 점화식 그대로 구현
        for(int i=3; i<1001; i++) {
            arr[i] = arr[i-1] + arr[i-2];
            arr[i] %= 10007;
        }
        System.out.println(arr[n]);
    }
}

 

 

채점 결과

11726번 채점 결과

문제 링크

• 11726번: 2×n 타일링 (acmicpc.net)