[C] 백준 2747 - 피보나치 수 | BaekJoon

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 45보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1

10

예제 출력 1

55

예상 풀이 방법

스택을 사용하여 풀어야 하는 문제다.
재귀를 사용하며 주어진 n이 2보다 크거나 같다면 (n-1) + (n-2)를 호출하는 방식으로 풀면 될 것 같다.

1차 코드

#include <stdio.h>

int fib(int n) {
    if (n >= 2) {
        return fib(n - 1) + fib(n - 2);
    }
    else if (n == 1) {
        return 1;
    }
    else
        return 0;

}

int main() {
    int n;
    scanf("%d", &n);
    fib(n);
}

1차 결과

출력 결과물 없음

1차 진단

솔직히 비슷한 문제를 저번에 풀어봐서 최대한 기억나는대로 따라쓰다보니 결론이 잘못되었다.
실행이 되는 것으로 보아 구성 상 문제는 없어보이는데 경고문 내용을 유심히 잘 보고 문제점을 파악해보도록 하자.

일단 반환값이 무시되었다는 점이 가장 문제가 큰 것 같다.

scanf로 받아서 사용자 지정 함수인 fib로 n을 들고 이동한다.

fib 함수는 재귀를 노리고 만든 함수이므로

if n이 2보다 크다면 fib(n-1) + fib(n-2) 를 호출한다.
이러면 n-1이 2일때까지 스택이 쌓이고 자기 자신을 계속 호출하며 피보나치 수열을 완성한다.

else if에는 만약 n이 1일 경우를 가정하여 n이 1이라면 return값을 1로 지정한다.

아닐 경우 변수 제외를 위해 return 0;를 삽입한다.

아 근데 여기서 return까진 줬는데 int형 사용자 지정 함수에 1이 반환될 경우 무언가의 작업이 있어야하는데

그게 없구나...

생각해보니까 반환 값이 무시되었다는 말도 scanf는 받았는데 printf도 없고 그래서 그런 것 같다.

fib(n); 대신에 이걸 프린트 값으로 써주자.

main 함수에 printf를 써주자. printf 할 수는 fib(n)이다.

2차 코드

#include <stdio.h>

int fib(int n) {
    if (n >= 2) {
        return fib(n - 1) + fib(n - 2);
    }
    else if (n == 1) {
        return 1;
    }
    else
        return 0;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d", fib(n));
}

2차 실행 결과

10
55

백준 실행 결과

2차 진단

변수다. 시간 초과가 처음 걸려봤다.
재귀로 푸니까 너무 오래걸려서 그런건가...
문제를 읽어보니 추가시간 없음이라고 강조해놓은 걸 보면 분명 내가 쓰는 이 방법을 쓰지말고 풀으라는 것 같다.

그럼 사용자 지정 함수를 사용하지 말고 풀어보는 방법으로 for문을 써서 풀면 될 것 같다.

3차 코드

#include <stdio.h>

int main() {
    int answer = 2;
    int arr[45] = { 0 };
    int n;
    scanf("%d", &n);

    // 일단 계산하기 까다로운 피보나치 수열의 1번째와 2번째를 예외처리
    // 2보다 작을 경우
    if (n < 2) {
        // 인데 0일 경우
        if (n == 0) {
            printf("0");
        }
        // 인데 1일 경우
        else {
            printf("1");
        }
    }

    else {
        for (int i = 2; i < n; i++) {
            arr[answer] = arr[i - 1] + arr[i - 2];
            arr[i - 1] = arr[i];
            arr[i - 2] = arr[i - 1];
        }
        printf("%d", arr[answer]);
    }
    return 0;
}

3차 실행 결과

10
0

3차 진단

되도않는 0을 쓴게 문제인 것 같다.
굳이 배열이 필요했나싶기도 한 느낌이다.

그냥 int a, b로 해서 재귀랑 비슷하게 만들어도 될텐데 뭐에 씌였나보다.

사실 배열만 만들고 오류나서 -172193713 이런 식으로 뜨길래 배열에 0값을 넣었더니 저 난리가 났다.

그냥 초창기에 배웠던 스왑 때 tmp 느낌처럼 활용해본다.

4차 코드

#include <stdio.h>

int main() {
    int a = 0;
    int b = 1;
    int answer;
    int n;
    scanf("%d", &n);

    // 일단 계산하기 까다로운 피보나치 수열의 1번째와 2번째를 예외처리
    // 2보다 작을 경우
    if (n < 2) {
        // 인데 0일 경우
        if (n == 0) {
            printf("0");
        }
        // 인데 1일 경우
        else {
            printf("1");
        }
    }

    else {
        for (int i = 1; i < n; i++) {
            answer = a + b;
            a = b;
            b = answer;
        }
        printf("%d", answer);
    }
    return 0;
}

4차 실행 결과

10
55

4차 백준 실행 결과

미흡했던 점

굳이 꼽으라면 이미 했던거라면서 기억을 더듬어서 풀려고 했던 태도.

오히려 그것 때문에 더 돌아간 느낌도 있긴 하다.

그리고 되도않는 배열 사용으로 문제를 한 번 더 조져놨던 것.

지식이 얕은 것이 티가 난다고 해야하나.

개선 방안

어라 해봤는데 금지, 배열 개념 재정립

최종 코드

#include <stdio.h>

int main() {
    int a = 0;
    int b = 1;
    int answer;
    int n;
    scanf("%d", &n);

    if (n < 2) {
        if (n == 0) {
            printf("0");
        }
        else {
            printf("1");
        }
    }

    else {
        for (int i = 1; i < n; i++) {
            answer = a + b;
            a = b;
            b = answer;
        }
        printf("%d", answer);
    }
    return 0;
}

비고

왜 해결되었는데도 C6031 반환 값이 무시되었습니다가 항상 뜨지 잘 안보였던 것 같은데