문제풀이(Problem Solving)

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

게임이 더 좋아 2021. 8. 31. 23:21
반응형
728x170

 

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

 

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];
    
    
}

 

쉬우니까 재밌지..

어려워지면 화가 난다.

무능력한 나에게ㅠㅠ

 

 

728x90
반응형
그리드형

'문제풀이(Problem Solving)' 카테고리의 다른 글

백준, BOJ, 9251번, LCS : C++ [CPP]  (0) 2021.09.04
백준, BOJ, 2293번 C++ [CPP] *  (0) 2021.09.01
백준, BOJ, 17298번 C++ [CPP]  (0) 2021.08.28
백준, BOJ, 1260번 C++ [CPP]  (0) 2021.08.28
백준, BOJ, 2003번 C++ [CPP]  (0) 2021.08.27