백준 algorithm
백준 2193 - 이친수
cosmohoo
2020. 4. 23. 17:39
반응형
=> DP 문제이다.
=> DP [i][j]
=> i : 몇 자릿수인지 나타냄
=> j : 어떤 숫자로 끝나는지 나타냄
-
DP[i][0] = DP[i-1][0] + DP[i-1][1]
-
=> 0으로 끝나는 수의 경수, 앞의 수가 1이어도 되고 0이어도 된다.
-
DP[i][1] = DP[i-1][0]
-
=> 1으로 끝나는 수의 경수, 앞의 수가 0이어야 된다.
위의 식대로 풀어도 된다.
본인은 하나씩 손으로 풀어보며 식을 세우게 되었다.
-
DP[i] = DP[i-1] + DP[i-2]
=> 위의 식을 통해 원하는 값을 얻을 수 있다.
<전체 코드>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
long DP[91]={0}; //DP array
DP[1] = DP[2] =1; // initializing DP
int N;
cin >> N;
for(int i=3; i< N+1; i++) //DP Calculating
{
DP[i] = DP[i-1] + DP[i-2];
}
cout <<DP[N]<<'\n';
}
반응형