대엉코딩

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;
}

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

다이나믹 프로그래밍을 이용하였습니다.

조건3개를 잘 파악한 후 고민을 좀 했는데

2번째 문제 조건을 잘 이용해야 했습니다.

목표계단을 무조건 밟아야 한다는 가정하에(조건3)

두가지 경우의 수가 나옵니다 (조건1)

1) 바로 전계단을 밟고 목표계단을 밟는경우

2) 전전계단을 밟고 목표계단을 밟는 경우

하지만 1번 조건을 그대로 적용할 경우 3번연속된 계단을 밟게 되는 경우가 생길수 있습니다.(즉 조건2 를 무시한 상태)

즉 전계단을 밟기전에는 전전전계단을 밟았어야 한다는 조건이 들어가야 합니다.(조건추가)

dp는 최대값을 저장한 배열이고 stairvalue는 각 계단의 값을 넣어놓은 배열 입니다.

<필기>

<코드>

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

간단한 다이나믹 프로그래밍 문제라고 할수 있겠습니다.

사실 처음 할때 개념을 이해하기가 꽤 힘들었던 것 같았던 기억이 있습니다....

이번에 아이패드를 사면서 사용하면서 풀고 있는데 보면서 약간 이해를 도울 수 있었으면 좋겠네요

목표지점 n으로 가기 위해 정수 123만 사용할수 있기 때문에

4이상의 숫자들은  1칸 가고 목표지점에 가는 경우의 수 dp[n-1]

                        2칸 가고 목표지점에 가는 경우의 수 dp[n-2]

                        3칸 가고 목표지점에 가는 경우의 수 dp[n-3]

으로 이해하시면 편하지 않을까 생각합니다.

<필기>

<코드>