[알고리즘] 백준 1904
문제
문제 링크
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];
}
Author And Source
이 문제에 관하여([알고리즘] 백준 1904), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@shininghyunho/알고리즘-백준-1904
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
/**
* 백준 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];
}
Author And Source
이 문제에 관하여([알고리즘] 백준 1904), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@shininghyunho/알고리즘-백준-1904저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)