[백준] 11727번 2xn 타일링 2 - Java, 자바

난이도

실버 3

문제

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

풀이

11726번 2xn 타일링 문제와 비슷하지만 2x2 타일이 추가되었다.

1. 테이블 정의하기
   D[i] = 2xi 크기의 직사각형을 1x2, 2x1, 2x2 타일로 채우는 방법의 수

2. 점화식 찾기
   

D[n]을 구하기 위해 왼쪽 가장 위 타일을 채우기 위한 방법을 찾아보니 위와 같은 방법을 생각했다.

따라서 점화식으로 표현하면 D[i] = D[i-1] + 2xD[i-2]

3. 초기값 정하기
   D[1] = 1
   D[2] = 3 <- 타일의 추가로 이전 문제와 달라짐

위 세 단계를 모두 채웠다면 코드를 작성할 수 있다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class boj_11727 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[1001];
        dp[1] = 1;
        dp[2] = 3;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
        }
        System.out.println(dp[n]);
    }
}