[Week 1] BOJ #1003 self review - yujungee

[yujungee]

BOJ #1003 self review

• 파일명: algo_2022/#1003.cpp (branch - yujungee)
• 수행시간: 4ms
• 메모리: 2020KB

1. 문제 해결 과정

처음엔 이걸 굳이 dp로 풀어야 하나?라는 생각이 들어 반복문으로 돌렸지만 시간 초과가 났다. (시간 제한 0.25 초)
이걸 dp로 풀려면 반복되는 문제가 존재해야 하는데 도대체 규칙이 뭔지 감이 안왔다.
그래서 그냥 0 과 1이 나오는 횟수를 N을 기준으로 써보았더니 피보나치 수열의 형태였다.

• N이 0~5 일 때 0과 1의 출력 횟수
  0: 1 → 0 → 1 → 1 → 2 → 3
  1: 0 → 1 → 1 → 2 → 3 → 5

2. 아이디어

• dp, 메모이제이션
• 피보나치 수열에서 fibonacci(1) = 1 → cache[1] = 1 미리 저장 시켜뒀다.
• N이 0일 때 cache 인덱스에 음수가 들어가므로 함수에 들어가지 않고 출력시킨다.

3. 코드 설명

• memset 함수를 통해 cache를 0으로 초기화하기 위해 cstring을 #include 해준다.

  #include <cstring> 

• fibonacci(int n) :

  int fibonacci(int n) {
      if (n == 0 || n == 1){    // n이 0과 1일 때는 바로 0, 1을 리턴해서 파라미터에 음수의 값이 들어가지 않도록 한다.
          return cache[n];
      }
      else if (cache[n] == 0) {    // 처음 푸는 문제일 때
          cache[n] = fibonacci(n-1) + fibonacci(n-2);
      }
      return cache[n];    // 이미 푼 문제임으로 답을 바로 리턴
  }

전체 코드 보기

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

int cache[41]={0};

int fibonacci(int n) {
    if (n == 0 || n == 1){
        return cache[n];
    }
    else if (cache[n] == 0) {
        cache[n] = fibonacci(n-1) + fibonacci(n-2);
    }
    return cache[n];
}

int main(){
    int tc;
    cin >> tc;
    int num;
    while(tc--){
        memset(cache, 0, sizeof(cache));
        cin >> num;
        cache[1]=1;
        if (num-1 < 0){
            cout << 1;
        }
        else{
            cout << fibonacci(num-1);
        }
        
        cout << " " << fibonacci(num) << endl;
    }
}