2022.03.19 84일차

백준 11726번 (2×n 타일링)

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

나의 풀이

1. n이 1일 때 -> 1개, n이 2일 때 -> 2개, n이 3일 때 -> 3개, n이 4일 때 -> 5개, .... n - 2 + n - 1 = n
2. 동적계획법 활용하기, 이전의 값을 활용하므로 10007 나머지 계산도 포함
3. n이 1과 2일 때는 1, 2 할당
4. dp값이 0보다 크면 값 불러오기

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

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

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

        System.out.println(funcDP(n));
    }

    static int funcDP(int n) {
        if (n == 1) {
            return dp[1] = 1;
        }

        if (n == 2) {
            return dp[2] = 2;
        }

        if (dp[n] > 0) {
            return dp[n];
        }

        return dp[n] = (funcDP(n - 2) + funcDP(n - 1)) % 10007;
    }
}

생각하기