백준 1904 c++ 풀이

안녕하세요 오늘은 다이나믹 프로그래밍을 이용한 문제를 풀어보겠습니다.

1

11 00

100, 111, 
001, 

1001, 1111, 0011,
0000, 1100

10011, 11111, 00111, 00001, 11001, 
10000, 11100, 00100 

f(n) = {f(n-1) + "1"} + {f(n-2) + "00"}

 

메모장에 끄적이면서 생각했습니다. 

 

f(n)의 경우는 f(n-1) 뒤에 "1"을 붙인 경우와, f(n-2) 뒤에 "00"을 붙인 경우를 합한것입니다.

따라서 개수는 f(n) = f(n-1) + f(n-2)입니다

이것을 구현하겠습니다

 

주의해야할 점:

v.at(n)이 int의 범위를 넘어가지 않도록 v.at(i)을 설정해줄때부터 15746을 계속 나눈 나머지를 대입합니다.

 

 

코드:

#include <bits/stdc++.h>
#include <vector>

using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	vector<int> v(1000002);

	int n;
	cin>>n;
	v.at(1) = 1;
	v.at(2) = 2;
	v.at(3) = 3;
	if(n<=3) cout<<n<<endl;
	else{
		for(int i = 4; i<=n; i++){
			if(v.at(i) == 0){
				v.at(i) = (v.at(i-1) + v.at(i-2))%15746;
			}
		}
		cout<<v.at(n);
	}
}