문제 링크

성능 요약

메모리: 14360 KB, 시간: 108 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 2월 12일 01:39:33

문제 설명

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

풀이

느낀점

• dp는 실버도 꽤 고민이 필요하다.
• 직접 그림을 그려보면서 규칙을 찾았다.

설계 : 20분

• 길이가 n인 직사각형을 타일로 채우는 방법은 n-1 길이의 직사각형 타일에 21 짜리 타일을 더하거나, n-2 길이의 직사각형 타일에 12 두개 또는 2*2 하나를 더하는 것이다.
• 따라서 dp[n] = dp[n-1] + (dp[n-2] * 2)
• 출력조건에 유의한다. dp테이블을 채울때 거쳐가는 모든 값에 대해서도 오버플로우를 대비한다. (10,007로 나눈 나머지)

코드(Java)

• 구현 시간: 5분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 2×n 타일링 2_11727
 * Date: 2025.02.12
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;

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

        bw.write(String.valueOf(dp[n]));
		bw.flush();
		bw.close();
		br.close();
	}
}