백준 1793 [C++]

www.acmicpc.net/problem/1793

1793번: 타일링

1. 풀이방법

- 점화식을 찾는 것은 어렵지 않습니다.

 

- 그림 몇개 그려보고 생각 해보면 dp[i]=dp[i-1]+dp[i-2]*2 입니다.

 

- 하지만 더 큰 문제는 c++에서 제공해주는 정수 자료형으로는 이 문제의 출력을 담아 낼 수 없습니다.

 

- 그래서 저 같은 이차원으로 벡터를 이용해서 벡터의 한 원소당 한 자리의 숫자를 담아서 표현하였고,

 

- 점화식을 보면 기껏해야 2를 곱하는 것이기 때문에 이것은 그냥 더하기로 구현이 가능하기 때문에

 

- 큰 정수의 덧셈을 구하는 함수만 작성하여 해결하였습니다.

 

 

 

2. 주의사항

- 일단 dp[0]=1 입니다 (  nCo = 1 인 것과 같이) -- 아무것도 선택 안함

 

- 그리고 처음에 while(EOF) 를 이용하여 입력을 제어 했는데, 출력초과가 계속 나와서 

 

- 이부분을 , while (cin>>n)로 해결했습니다.

 

 

 

3. 나의코드

#include<bits/stdc++.h>
using namespace std;




vector<int> bigintadd(vector<int> v1, vector<int> v2) {

	if (v1.size() < v2.size()) { // v1이 항상 더 큰수
		vector<int> tmpv = v1; v1 = v2; v2 = tmpv;
	}
	vector<int> result(v1.size());
	for (int i = 0; i < v1.size(); i++) {
		result[i] = 0;
	}
	if (v1.size() == v2.size() && (v1[v1.size() - 1] + v2[v2.size() - 1]) >= 10) {
		result.push_back(0); //사이즈 하나 증가
	}

	for (int i = 0; i < v2.size(); i++) {
		int tmpi = v1[i] + v2[i]+result[i];
		if (tmpi >= 10) { result[i + 1] += 1; result[i] =( tmpi-10); }
		else result[i] = tmpi;
	}
	for (int i = v2.size(); i < v1.size(); i++) {
		result[i] += v1[i];
	}

	return result;
}

// 점화식 dp[i]=dp[i-1]+dp[i-2]*(3-1)
// 큰수의 곱을 구현해야 한다.

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	vector<int> dp[251];
	dp[0].push_back(1); dp[1].push_back(1); dp[2].push_back(3);
	for (int i = 3; i <= 250; i++) {
		dp[i] = bigintadd(dp[i - 1], bigintadd(dp[i - 2], dp[i - 2])); //8은 171 7은 85   171+85+85
	}
	int n;
	while (cin>>n) {
		for (int i = dp[n].size() - 1; i >= 0; i--) {
			cout << dp[n][i];
		}
		cout << "\n";
	}
	return 0;
}