[코드트리] 2024/08/28 - 사각형 채우기2

사각형 채우기 2

내 풀이

• DP 문제로, 2 * n 크기의 사각형을 만들기 위해서는
  n - 1 사각형에 세로 사각형 1개를 붙이는 방식과
  n - 2 사각형에 정사각형 1개 또는 가로 사각형 2개를 붙이는 방식
  2가지로 2 * n 크기의 사각형을 만들 수 있다.
• 이와 같은 사각형 DP문제의 경우, 이전에 구해진 개수에 새로운 타일을 추가해 새로운 사이즈의 사각형을 만드는 것을 DP로 구현하면 된다.

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

public class Main {
    public static final int MAX_N = 1000;
    public static final int MOD = 10007;

    public static int n;
    public static int[] dp = new int[MAX_N + 1];

    public static void main(String[] args) throws IOException {
        init();

        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 3;

        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 2] * 2 + dp[i - 1] * 1) % MOD;
        }

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

    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
    }
}