[백준/실버] 1003번 피보나치 함수

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

피보나치 함수, 실버 3, 1003번

 

문제 자체는 되게 할 만 했는데 실수를 해서 시간이 많이 걸렸습니다.

중간 중간 연락이 많이 와서 계속 집중 못한게 큰 듯 합니다 (머쓱)

인ㅆr의 life란... (아님)

 

-

 

가장 바보같은 부분이자 제일 크게 배웠던 부분이었던 건

int cntZ[41] = { -1 };

로 코드를 짰다가 어.. 왜 초기화 안됬지...

전체 초기화는 0만 된다는 것을 까먹고 있었습니다(....)

어찌저찌 memset()으로 바로 초기화...

 

그거랑 N = 40까지인데

아무 생각 없이 평소대로 배열의 크기를 40으로 지정해주고

인덱스 40에 접근하고 있었던 것 ㅋㅋㅋㅋ

똑똑한 비주얼 스튜디오 덕분에 금방 다시 고치긴 했습니다만...

바보...

 

그래도 간만에 힌트 안 보고 문제를 풀어서 기분이 좋군요...

(그야 실버잖아)

(실버도 어려운 거 많거든)

(아유 그러세요.)

 

참, memset()의 경우도 VS에서 쳤을때는 바로 됬는데

백준에서 돌리니까 헤더가 없어서 오류가 나더군요.

몰론 써주는 쪽이 표준에 맞겠습니다만 신기했습니다. (편-리)

 

어쨌든 문제는 재귀함수를 이용한 피보나치 수열 함수의 개선입니다.

 

-

 

분할과 정복은 재귀함수를 통해 자연스레 달성되지만

N이 최대 40이기 때문에 그대로 구현하면 당연히 엄청난 시간이 걸립니다.

 

이를 DP를 이용해서 개선시킵니다.

메모이제이션을 이용해 (거창하지만 별 것 없이, 필요한 값을 기억해 놓는 것입니다)

작은 수부터 차례대로 현재 n의 0이 나온 횟수와 1이 나온 횟수를 구해 저장합니다.

이후 소소한 가지치기의 도움을 받아 앞서 계산했던 n이라면 중복 계산하지 않고 빠져나옵니다.

 

중복되는 연산이 많은 만큼 현저하게 속도가 향상됩니다.

궁금해서 원래 버전과 개선 버전을 둘 다 돌려보았는데,

원래 버전은 T=5, N=모두 40에 대해 30초가 넘도록 답을 모두 내지 못했고

개선 버전은 1초도 걸리지 않았습니다.

당연한 결과이긴 합니다... 그냥 저장했던 값을 출력하도록 했으니까요.

그래도 알고리즘의 힘을 이런 식으로 확인해보는 것도 재미있는 일인 것 같습니다.

 

제 경우 문제풀이가 익숙치 않아 문제를 읽자마자 DP가 바로 떠오르진 않았습니다만

어차피 시간을 개선해야겠다고 생각하니 그것밖에 떠오르는게 없더군요...

 

아래는 코드입니다만 어려운 문제는 아니니,

먼저 시도해보시고 막혔을 때 참고하시는 쪽을 추천드립니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <memory.h>
#include <vector>
using namespace std;

int cntZ[41];
int cnt1[41];

void fibonacci(int n) {
    if ((cntZ[n] != -1) && (cnt1[n] != -1)) { //체크를 했으면 연산 x (프루닝)
        return;
    }

    fibonacci(n - 1);
    fibonacci(n - 2);

    cntZ[n] = cntZ[n - 1] + cntZ[n - 2]; //+1 as it was -1
    cnt1[n] = cnt1[n - 1] + cnt1[n - 2];
}

int main(void) {
    int T;
    scanf("%d", &T);
    vector<int> v;

    memset(cntZ, -1, sizeof(int) * 41);
    memset(cnt1, -1, sizeof(int) * 41);

    for (int i = 0; i < T; i++) {
        int num;
        scanf("%d", &num);
        v.push_back(num);
    }

    //0일때는 0이 한번 나왔음
    cntZ[0] = 1;
    cnt1[0] = 0;

    //1일때는 1이 한번 나왔음(1은 더 나누어지지 못하므로)
    cntZ[1] = 0;
    cnt1[1] = 1;

    for (int i = 0; i < T; i++) {
        fibonacci(v[i]);
        printf("%d %d\n", cntZ[v[i]], cnt1[v[i]]);
    }
}

 

 

모든 분들 공부 화이팅입니다 >:3c