대엉코딩

www.acmicpc.net/problem/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;
}

www.acmicpc.net/problem/11726

1. 풀이방법

- 이 문제를 접할 때 점화식을 생각해내는 게 생각보다 어려웠습니다.

- 물론 이런 류의 문제는 알고나면 매우 간단하기는 하지만......!

- 결국 점화식은 dp[n]=dp[n-1] + dp[n-2] 입니다 

- 그림을 보시면 이해가 쉬우실 듯 합니다.

2. 주의사항

- 값을 저장할 테이블을 구성해서 메모이제이션을 활용하여 시간을 단축시켜주었습니다.

- 탑다운 방식으로 재귀함수만을 이용하여 연산하는 경우 중복되는 연산을 너무나 많이 하기때문에

- TIME LIMIT을 만나실 수 있습니다.

- 저장되어있는값이 있으면 바로 리턴해서 가져다 쓰고 새로운 값이면 테이블에 저장을 한 후 리턴해서

- 다음부터는 그 값이 필요할 때 테이블에서 바로 가져다 쓸 수 있도록 하면 됩니다.

3. 나의코드

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

int  n;
int dp[1001];

int getdpvalue(int num) {
	if (dp[num] == 0) { 
		dp[num] = (getdpvalue(num - 1) % 10007 + getdpvalue(num - 2) % 10007);
		return dp[num] % 10007;
	}
	else return dp[num]%10007;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	dp[1] = 1; dp[2] = 2; dp[3] = 3; // 3을 초기화안해줘도 되긴하다
	                                 // (하지만 경우의수 그림 그려놨으니까..아까워서)
	cout<<getdpvalue(n)<<"\n";

	return 0;
}