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

 

---

문제

• 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 문제.

 

아이디어

• 각 경우의 수를 나열해보면 다음과 같다.
  • 1, 3, 5, 11, 21, ...
• 이 규칙을 분석해보면 다음의 점화식을 얻을 수 있다.

$$a_{n} = a_{n-1} + 2a_{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] = 3;
        
        // 점화식 구현
        for(int i=3; i<1001; i++) {
            arr[i] = arr[i-1] + arr[i-2] * 2;
            arr[i] %= 10007;
        }
        System.out.println(arr[n]);
    }
}

 

 

채점 결과

11727번 채점 결과

 

문제 링크

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