[BOJ][DP][실3][1003] 피보나치 함수

문제 링크

피보나치 함수/실3

첫 번째 풀이 : 다이나믹 프로그래밍, Top-Down

Info Notice: 개인적으로 Top-Down 방식이 Bottom-up보다 어려웠던 문제입니다.

알고리즘

dp[i][0] : i를 인자로 전달했을 때 0을 출력하는 횟수
dp[i][1] : i를 인자로 전달했을 때 1을 출력하는 횟수

dp[i][0] = dp[i-1][0] + dp[i-2][0];
dp[i][1] = dp[i-1][1] + dp[i-2][1];

방문 여부를 저장하는 방법을 사용합니다.

dp[n][0] += fibo(n - 1).first; 부분에서 n이 1을 만날 때까지 계속 n이 줄어들면서 call stack이 쌓입니다. fibo(5)을 호출했다면 fibo(4) > fibo(3) > fibo(2)까지 계속 스택에 쌓이다가 fibo(2)에서으로 {0,1} + {1,0}를 return 받습니다. fibo(2)의 return 값을 받은 fibo(3)은 fibo(1)을 즉시 return받습니다. fibo(4)가 호출한 fibo(2)는 방문처리에 의해서 즉시 return됩니다.

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX 41

int dp[MAX][2];
bool visited[MAX];
using namespace std;
int a = 0, b = 0;

pair<int, int> fibo(int n) {
  if (n == 1) return { 0,1 };
  else if (n == 0) return { 1,0 };
  
  if (visited[n]) return { dp[n][0], dp[n][1] };
  visited[n] = true;
  
  dp[n][0] += fibo(n - 1).first;
  dp[n][1] += fibo(n - 1).second;
  dp[n][0] += fibo(n - 2).first;
  dp[n][1] += fibo(n - 2).second;
  
  return { dp[n][0], dp[n][1] };
}

int main(void) {
  //freopen("input.txt", "r", stdin);

  int n = 0;
  cin >> n;

  for (int i = 0; i < n; i++) {
    int m = 0;
    cin >> m;
    memset(dp, MAX, 0);
    pair<int, int> ans = fibo(m);
    cout << ans.first << " " << ans.second << "\n";
  }
  return 0;
}

두 번째 풀이 : 다이나믹 프로그래밍, Bottom-Up

알고리즘

dp[i][0] : i를 인자로 전달했을 때 0을 출력하는 횟수
dp[i][1] : i를 인자로 전달했을 때 1을 출력하는 횟수

dp[i][0] = dp[i-1][0] + dp[i-2][0];
dp[i][1] = dp[i-1][1] + dp[i-2][1];

값을 미리 구해두는 방법을 사용했습니다.

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX 41

int dp[MAX][2];
bool visited[MAX];
using namespace std;
int a = 0, b = 0;

int main(void) {
  //freopen("input.txt", "r", stdin);

  int n = 0;
  cin >> n;

  dp[0][0] = 1;
  dp[0][1] = 0;
  dp[1][0] = 0;
  dp[1][1] = 1;

  for (int i = 2; i <= 40; i++) {
    dp[i][0] = dp[i - 1][0] + dp[i - 2][0];
    dp[i][1] = dp[i - 1][1] + dp[i - 2][1];
  }

    for (int i = 0; i < n; i++) {
        int m = 0;
        cin >> m;
    cout << dp[m][0] << " " << dp[m][1] << "\n";
    }
  return 0;
}

결론

Success Notice: 다이나믹 프로그래밍의 쉬운 문제를 top-down, bottom-up 두 가지 방법으로 풀어봤습니다. 두 가지 모두 i에 대한 반복문에서 dp[i]를 구한다는 공통점이 있습니다. 수고하셨습니다.