백준 2193 - 이친수

문제 설명

 

 

=> 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';
    
}

 

 

 

 

 

 

 

 

 

 

 

 

실행화면 1

 

 

 

 

실행화면 2