[백준] 1793번:타일링 (C++)

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

1793번: 타일링

이 문제 점화식은 간단하다. 2x1칸이 오른쪽에 추가 되었을때, 새롭게 타일을 채우는 방법은 총 3가지 케이스이다.

추가 후 현재 타일이 2xN 이라고 할때,

1. 기존 2x(N-1) 타일 + 1개의 2x1 타일

2. 기존 2x(N-2) 타일 + 2개의 1x2 타일

3. 기존 2x(N-2) 타일 + 1개의 2X2 타일

 

즉, dp[N]가 2 X N 타일을 채우는 방법의 수라고 할때 점화식은 다음과 같다.

dp[i] = dp[i-1] + dp[i-2] + dp[i-2] 

 

이렇게 순탄하게 풀리는줄 알았지만, 평소처럼 구현하면 N이 커짐에 따라 방법의 수가 기하급수적으로 늘어나서 long long 배열로는 어림도 없었다. 테스트 케이스만 보아도 N이 100일때, 845100400152152934331135470251이다. N이 250까지므로, 굉장히 큰수가 나오므로 스택오버플로우가 난다....  그럼 어떻게 풀어야할까?

 

long long 보다 큰 숫자들을 덧셈을 구현해야 할땐, string으로 접근하여야 한다. C++에서 큰수 연산시 String을 사용하는 방법은 템플릿이 존재하므로, 코드는 보고 이해하고 동작방식만 예시를 들어서 설명해보겠다.

---

[Example]

A= 35, B = 7 , C = 777, sum = 0, result = 0

 

5 + 7 + 7 = 19 -------> sum=1 , result = 9

3 + 7 + sum = 11 --------> sum=1, result = 91

7 + sum = 8 -------> sum=0, result = 918

result = 819

 

원래 우리가 하던 덧셈계산처럼 각 숫자의 뒷자리부터 하나씩 계산하고, 올림 수를 저장하는 방식이다. sum은 올림수를 저장하는 변수, result는 총 합을 저장하는 변수이다. 다만, 편의상 result에 숫자를 뒤로 push하기 때문에, 계산이 끝나고 reverse함수를 통해 바꿔주면된다. 

 

추가적으로, N이 0일때 (타일이 없을때) 아무것도 안하는 것도 1가지로 계산해야하므로, 초기값을 1로 주었다. 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int N;
string dp[251] = { "1","1","3" };
int largest=2;

//점화식 : dp[i] = dp[i-1] + 2*dp[i-2] = dp[i-1] + dp[i-2] + dp[i-2]

//문자열을 통한 큰 수 덧셈
void string_add(int from, int to) {
	for (int i = from; i <= to; i++) {
		string a = dp[i - 1], b = dp[i - 2], c = dp[i - 2];
		int sum = 0;
		string result; //숫자들을 뒤에서부터 더해서 저장 
		while (!a.empty() || !b.empty() || !c.empty() || sum) { //모두 빈문자열이거나 올림수가 더이상 없는경우
			if (a != "") {
				sum += a.back() - '0'; //string to int
				a.pop_back();
			}
			if (b != "") {
				sum += b.back() - '0';
				b.pop_back();
			}
			if (c != "") {
				sum += c.back() - '0';
				c.pop_back();
			}
			result.push_back(sum % 10 + '0'); //다 더했을때 마지막자릿수
			sum /= 10; //올림수
		}
		reverse(result.begin(), result.end()); //거꾸로 계산했으므로
		dp[i] = result;
	}
}

int main() {
	while (cin >> N) {
		if (largest < N) {
			string_add(largest, N);
			largest = N;
		}
		cout << dp[N]<<endl;
	}
}