[알고리즘] 백준 1904

1212 단어 알고리즘DPDP

문제

문제 링크
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];
}

좋은 웹페이지 즐겨찾기