백준 1793번 타일링 (C++)

문제 링크 : www.acmicpc.net/problem/1793

1793번: 타일링

이 문제는 백준 11727번 2xn 타일링 2의 확장판이다.

문제의 출력에서 확인할 수 있듯이, 무턱대고 숫자형으로 문제에 접근했다가는 시간초과 내지는 Stack Overflow가 발생할 수 밖에 없다. 이를 방지하고자 문자열로 접근해야한다. 

 

문제 풀이는 다음과 같다. 

1. 백준 11727번과 동일하게, 이 문제의 2*n의 타일을 채울 방법은 (n-1)번째 + (n-2)번째 + (n-2) 번째 타일을 채우는 합과 동일하다. 이해가 가지 않을 경우 위의 11727번 링크를 확인해보자.

2. 입력은 숫자형으로 받지만 계산은 문자열로 해야한다. 때문에 숫자형을 문자로 계산하는 방식을 활용한다. C++에서 큰 수연산을 위해 문자열을 활용하는 방식으로 전형적인 템플릿이 존재하므로, 아래 공식을 이해하면 된다.

 

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

string ans[251];

void tile(int n) {
	for (int i = 4; i <= n; i++) {
		string temp = "", n1 = ans[i - 1], n2 = ans[i - 2], n3 = ans[i - 2];
		int sum = 0;
		while (!n1.empty() || !n2.empty() || !n3.empty() || sum) { // while(sum)은 sum!=0과 같은 뜻
			if (n1 != "") {
				sum += n1.back() - '0';
				n1.pop_back();
			}
			if (n2 != "") {
				sum += n2.back() - '0';
				n2.pop_back();
			}
			if (n3 != "") {
				sum += n3.back() - '0';
				n3.pop_back();
			}
			temp.push_back((sum % 10) + '0');
			sum /= 10;
		}
		reverse(temp.begin(), temp.end());
		ans[i] = temp;
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	ans[0] = '1', ans[1] = '1', ans[2] = '3', ans[3] = '5'; // 주의. ans[0] = 1이다!
	string n = "";
	while (cin >> n) { // 입력값이 계속 주어지는 한 while은 멈추지 않음
		int temp = stoi(n);
		if (ans[temp]!="") cout << ans[temp] << "\n";
		else {
			tile(temp);
			cout << ans[temp] << "\n";
		}
	}
	return 0;
}

한 번 틀렸습니다를 겪었는데, 33%쯤에서 틀려버리고 말았다. 

이유는 단순했다. 배열 ans[0]을 1로 초기화 해야했는데, 0으로 초기화하고 말았다. 

ans[0]이 1인 이유는 조합에서 nC0의 경우, 결과는 1로 인정되기 때문이다.

더 단순히 설명하자면, 아무것도 내지 않는 것도 하나의 방법이므로 정답은 1이 된다.