문제

문제 링크
00과 1 로 N개의 숫자를 표현하는 방법의 수를 구하는 문제다.

dt(k)를 k번째 방법의 수라고하면
dt(1)=1,dt(2)=2이다.

여기서 3번째를 구하는 방법은 dt(1)에 00을 붙이고 dt(2)에 1을 붙였을때 경우를 더한것이다.

즉 점화식으로 표현하면
dt(k)=dt(k-1)+dt(k-2) 다.
초기값은 dt(1)=1,dt(2)=2 (편의상 k번째 배열에 k번째 값을 넣기위해 0을 임의로 추가했다.)

사실 숫자 몇으로 나누라고하면 dp인 경우가 대부분이었다.
그리고 배열을 vector를 사용했는데 기본자료형 배열은 25만정도까지 밖에 선언할수가없다.
vector는 몇억 정도까지 가능하다.
n이 100만까지여서 vector를 사용했다.

code

/**
 * 백준 1904
 * dp
 * 00과 1 로 N개의 숫자를 표현하는 방법의 수
 * dt[k]=dt[k-1]+dt[k-2]
*/
#include <bits/stdc++.h>
using namespace std;

int divNum=15746;

int main(void){
    int n;
    cin>>n;
    vector<int> dt;
    dt.push_back(0);
    dt.push_back(1);
    dt.push_back(2);
    for(int i=3;i<=n;i++){
        int val=(dt[i-1]+dt[i-2])%divNum;
        dt.push_back(val);
    }
    cout<<dt[n];
}