백준, BOJ, 2193번 C++ [CPP]

 

다이나믹 프로그래밍이 재밌어지는 시기

 

https://www.acmicpc.net/problem/2193

 

 

---

 

우선 예를 몇개 들고나보면

하위 문제로 쪼개지는 것을 알 수 있고

하위 문제에 대해 답을 구하면 된다.

 

 

재귀함수로 구현을 해보고

해당 함수를 Memoization 하게되면 시간 안에 풀어진다.

 

#include <iostream>

using namespace std;


int N;

long long dp[91][2];



int main(){
    cin >> N;
    
    dp[1][1] = 1;
    dp[2][0] = 1;
    
    for(int i = 3; i<=N; i++){
        dp[i][0] = dp[i-1][0] + dp[i-1][1];
        dp[i][1] = dp[i-1][0];
    }
    
    
    cout << dp[N][0]+dp[N][1];
    
    
}

 

쉬우니까 재밌지..

어려워지면 화가 난다.

무능력한 나에게ㅠㅠ