[BOJ][C++] 1793번 타일링

https://www.acmicpc.net/problem/1793

공부 날짜 : 2024.12.13
정답 참조 여부 : X

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

---

간단한 dp문제.... 인줄 알았다.

점화식 자체는 쉽다.
$dp[i] = dp[i-1] + 2 * dp[i-2]$

하지만 n이 250까지 가기 때문에 unsigned long long 범위를 벗어난다.

이를 위해 숫자를 한자리씩 계산하여 최대 100자리 까지 계산 할 수 있도록 계산해야하고, 테스트 개수를 알려주지 않기때문에 종료조건을 잘 판단해야 한다.

어려운 문제는 아니여서 포스팅을 안하려다가 1자리씩 계산하여 매우 큰 수의 계산을 해본 경험이라 작성했다.

ps) 종료조건의 경우

int x;
while(stc::cin >> x){}

로 작성하면 파일의 끝이나 EOF를 만났을때 자동으로 종료한다고 한다(처음 알았음...)

#if 1
#include <iostream>

int* dp[251];

//값이 너무 크므로 1자리씩 계산
int* add(int* a, int* b) {
	// dp[250]이 100은 안넘겠지
	int* ans = new int[100];

	// 항상 a가 더 크다.
	if (a[0] < b[0]) {
		int* temp = a;
		a = b;
		b = a;
	}

	ans[0] = 0;
	int i = 1;
	while (i <= b[0]) {
		ans[i] = 0;
		ans[i] += ans[i - 1] / 10;
		ans[i - 1] %= 10;
		ans[i] += a[i];
		ans[i] += b[i];
		++i;
	}

	while (i <= a[0]) {
		ans[i] = 0;
		ans[i] += ans[i - 1] / 10;
		ans[i - 1] %= 10;
		ans[i] += a[i];
		++i;
	}

	if (ans[i - 1] / 10) {
		ans[i] = 0;
		ans[i] += ans[i - 1] / 10;
		ans[i - 1] %= 10;
		++i;
	}

	ans[0] = i - 1;

	return ans;
}

int main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0); std::cout.tie(0);

	dp[0] = new int[100];
	dp[0][0] = 1;
	dp[0][1] = 1;
	dp[1] = new int[100];
	dp[1][0] = 1;
	dp[1][1] = 1;

	for (int i = 2; i <= 250; ++i)
		//dp[i] = (2 * dp[i-2]) + dp[i-1];
		dp[i] = add(add(dp[i - 2], dp[i - 2]), dp[i - 1]);

	//int T; std::cin >> T;
    int n;
	while(std::cin >> n) {
		for(int i = dp[n][0]; i>0; --i)
			std::cout << dp[n][i];
		std::cout << "\n";
	}
}


#endif