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;
}
'알고리즘 문제풀이 > 다이나믹 프로그래밍' 카테고리의 다른 글
백준 3687 [C++] (0) | 2021.08.09 |
---|---|
백준 1103 [C++] (0) | 2021.07.06 |
백준 1965 [C++] (0) | 2021.02.03 |
백준 1463 [C++] - 메모리초과 (0) | 2020.12.15 |
백준 11048 [C++] (0) | 2020.12.14 |