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

문제 링크

성능 요약

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

분류

다이나믹 프로그래밍

제출 일자

2024년 9월 10일 21:19:58

문제 설명

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

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

입력

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

출력

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

제출

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;
int N;
int dp[1001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	freopen("input.txt", "r", stdin);

	cin >> N;

	dp[1] = 1;
	dp[2] = 2;
	
	for (int i = 3; i <= N; i++)
	{
		dp[i] = dp[i - 1] + dp[i - 2];
		dp[i] %= 10007;
	}

	cout << dp[N];
}

풀이 과정

몇단계 그려보면 단계별 숫자에 대해 규칙이 보인다.

1일때, 1 2일때, 2 ..

1, 2, 3, 5, 8 ...

피보나치 수열의 결과값과 같다!

그렇다면 dp[] 배열을 생성하고 점화식을 생성하여 방법의 수(dp[N])를 구하는 반복문을 구성하였다.

에러 발생

처음에는 마지막 cout 출력에만 10007으로 나눈 나머지를 구했으나 잘못된 생각이였다.

애초에 int형 배열인 dp[N] 에서 N이 500 정도만 되어도 오버플로우가 발생한다.

만에하나 중간 과정에서 오버플로우가 발생하지 않는다는 가정하에, 마지막 결괏값에 10007을 나눈 나머지든

반복문에서 dp에 저장할때 계속해서 10007으로 나누어 저장해도 두 결괏값은 차이가 없다.

dp[i] %= 10007; 을 반복문에 추가해 해결하였다.