1. 백준 1003 피보나치 함수 문제 공부

1. 문제를 풀면서

 백준 온라인 저지에서 푼 문제를 내 블로그에 다루려고 한다. '동적 계획법 기초 단계'의 첫 문제는 피보나치 함수 관련된 문제이다. 이 문제에서 주어지는 조건은 동적 계획법이 아닌 방식으로도 쉽게 풀 수 있게 해줬다. 하지만 조건(구하려는 N번째 피보나치 수의 N)이 최대 40으로 정해지지 않았다면 동적 계획법을 사용해야 했을 것이다. 이는 피보나치 수를 구하는 알고리즘에 동적 계획법을 적용하는 것에 대해 생각해 보라는 뜻을 주는 문제가 아닌가 싶었다. 

2. 문제 출처 및 보기

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

3. 내 소스코드

 이 문제는 딱히 설명이랄게 없다. 동적 계획법을 사용한 것이 아니고, 0과 1이 반환되는 상황마다의 카운트를 출력해주었다.

#include<iostream>
#include<vector>
using namespace std;
 

int count0, count1;
vector<int> count0_vec, count1_vec;
 
int fibo(int n) {
    if (n == 0) {
        count0++;
        return 0;
    }
    else if (n == 1) {
        count1++;
        return 1;
    }
    else
        return fibo(n - 1) + fibo(n - 2);
}
 
int main() {
    int T, N;
 
    // 데이터 입력 및 문제 해결
    scanf("%d", &T);
    for (int t = 0; t < T; t++) {
        scanf("%d", &N);
        count1 = count0 = 0;
        fibo(N);
        count0_vec.push_back(count0);
        count1_vec.push_back(count1);
    }
 
    // 결과 출력
    for (int idx = 0; idx < count0_vec.size(); idx++)
        printf("%d %d\n", count0_vec[idx], count1_vec[idx]);
 
    return 0;
}

 추가로 동적 계획법을 적용한 피보나치 수를 구하는 소스코드를 작성했다. (In VS 2017 Community)

#include<iostream>
using namespace std;
 
int dp[100000];
 
int fibo(int n) {
    if (n == 0) {
        return 0;
    }
    else if (n == 1) {
        return 1;
    }
    else if (dp[n] == -1){
        dp[n] = fibo(n - 1) + fibo(n - 2);
        return dp[n];
    }
    else
        return dp[n];
}
 
int main() {
    int N, answer;
 
    fill_n(dp, 41, -1);
    scanf_s("%d", &N);
 
    answer = fibo(N);
    printf("%d\n", answer);
 
    system("pause");
    return 0;
}