코딩 테스트 준비 1단계 기본기 - 백준 10870

코딩테스트 대비를 위해 도움이 될만한 문제 추천 블로그가 있어서 이 단계대로 코테를 준비합니다.

참조 사이트: http://covenant.tistory.com/224

코딩테스트 대비를 위한 백준 문제 추천

Part 1 준비운동 - 피보나치수 5 (백준 10870)

문제 출처: https://www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

풀이

일반적인 풀이로 풀고 예전에 피보나치 최적화 관련 글을 업로드 했던 적이 있어서(https://jow1025.tistory.com/101)

dp로도 풀어보았습니다. (벌써 업로드 한지 1년이 넘었네요 시간 참;;;)

 

코드

#include<iostream>
using namespace std;
int dp[21];
int func(int n);
int func_dp(int n);
int main()
{
    int n;
    cin >> n;
    /* func: 일반적인 풀이
       func_dp: dp를 이용한 풀이*/
    //cout << func(n) << endl;
    cout << func_dp(n) << endl;
 
    return 0;
}
//일반적인 풀이
int func(int n)
{
    if (n == 0) return 0;
    if (n == 1 || n == 2)return 1;
    return func(n - 1) + func(n - 2);
}
int func_dp(int n)
{
    if (n == 0) return 0;
    if (n == 1 || n == 2)return 1;
    //값이 담겨있으면 바로 반환
    if (dp[n] != 0)
        return dp[n];
    return dp[n] = func_dp(n - 1) + func_dp(n - 2);
 
}
 

 

결과