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

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

 

해설

n이 1, 2, 3, 4일 때 직접 손수 그려보면 패턴이 보인다. 

n >= 3 일 때는 (n - 2)일 때와 (n - 1)일 때를 고려해야 한다.

• (n - 2)와 n은 2개의 타일 차이가 발생한다. 2개의 타일을 쓸 수 있는 경우의 수는 아래와 같다.
  • ll
  • --
    --
• (n - 1)과 n은 1개의 타일 차이가 발생한다. 1개의 타일은 경우의 수가 1개이다.
  • |

설명보단 사진으로 이해하기가 더 편할 것이다!

 

코드

import java.io.*;

public class Main {

    static int n;
    static int[] dp;

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

        n = Integer.parseInt(br.readLine());
        dp = new int[1001];
        dp[1] = 1;
        dp[2] = 3;

        recur(n);
        System.out.println(dp[n]);
    }

    static void recur(int num) {
        for (int i = 3; i <= num; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
        }
    }
}