[백준 11726] 2*n 타일링 (Java)

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

11726번: 2×n 타일링

접근 방법

규칙을 찾아 점화식을 도출해 내야하는 DP 문제였다.

점화식 자체는 찾아내는데 크게 어렵지 않았다.

 

하나하나 그려가며 합을 비교해보면

dp(n) = dp(n-1) + dp(n-2)의 점화식이 어렵지 않게 도출된다.

 

문제는 왜 그런가였다.

아래 그림과 같이 비교해보고 쉽게 알 수 있었다.

n = 1일 때는 세워진 타일 1개

n = 2일 때는 두 개의 세워진 타일과 눕혀진 타일로 총 2개였다.

n = 3일 때부터는 맨 뒤의 타일이 [한 개의 세워진 타일인 경우]와 [두 개의 눕혀진 타일]로 구분해 놓고 나머지 부분을 봤더니

한 개 세워진 경우는 그 이전의 n-2인 2의 경우와 동일했고, 두 개 눕혀진 경우는 n-3인 1의 경우와 동일했다.

이러한 규칙성이 계속해서 적용되었기 때문에 n인 경우에는 n-1과 n-2인 경우의 갯수를 더한 값이 된다.

 

 

소스 코드

import java.util.Scanner;

public class Main {
    private static int[] dp = new int[1001];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        dp[1] = 1;
        dp[2] = 2;

        int answer = solution(n);

        System.out.println(answer);
    }

    private static int solution(int n) {
        if (n == 1) {
            return dp[1];
        } else if (n == 2) {
            return dp[2];
        }

        if (dp[n] != 0) {
            return dp[n];
        } else {
            dp[n] = solution(n - 1) + solution(n - 2);

            return dp[n] % 10007;
        }
    }
}