[Silver III] 2×n 타일링 2 - 11727

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

다이나믹 프로그래밍

제출 일자

2026년 2월 5일 20:44:09

문제 설명

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

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

입력

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

출력

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

접근방법

점화식을 먼저 도출해낸 후 -> dp[n] = dp[n-1] + dp[n-2] + dp[n-2] Topdown이되 메모이제이션을 사용해 O(n) 복잡도를 가지도록 구현하였다.

제출

// 11727
// 
// dp : 문제를 작은 문제로 나누어 해결
// 점화식 : dp[n] = dp[n-1] + dp[n-2] + dp[n-2]
// 
// - 복잡도
// 메모이제이션을 적용한 O(n)
// 
// - 자료구조
// 배열 int[]
#include <bits/stdc++.h>

std::vector<int> dp(1001);

int D(int n)
{
	if (dp[n] != 0) {
		return dp[n];
	}
	return dp[n] = (D(n - 1) + 2 * D(n - 2)) % 10'007;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int N;
	dp[1] = 1;
	dp[2] = 3;
	std::cin >> N;
	std::cout << D(N);

	return 0;
}

다른 풀이

topdown을 하더라도, 모든 n을 거치기 때문에 재귀를 사용하지 않고 루프문을 통한 bottomup 방식을 사용하는것이 괜찮은 대안이겠다.

// ...main중에서
dp[1] = 1;
dp[2] = 3;
std::cin >> N;
for (int i = 3; i<=N; i++){
    dp[N] = dp[N - 1] + 2 * dp[N - 2];
}
// ...