[백준] 1003번 피보나치 함수 ( 파이썬 / c언어 )

│문제

1003번: 피보나치 함수

 

 

│풀이 (Python)

def fibo(n):

    if n<2:

        if n==0:

            print(1,0)

        else:

            print(0,1)

    else:

        for i in range(1,n):

            arr.append([arr[i-1][0]+arr[i][0],arr[i-1][1]+arr[i][1]])

        print(*arr[-1])

T=int(input())

for i in range(T):

    arr=[[1,0],[0,1]]

    fibo(int(input()))

 

│설명  (Python)

keypoint 1 -  DP 또는 피보나치에 너무 얽매여있으면 안 된다.

 

필자도 피보나치 함수에 관한 문제를 보는 순간 자동반사적으로 재귀함수에 신경을 쓰게 된다.

 

 

첫 풀이에서는 왼쪽 기본코드에서 print문 대신 count변수를 활용하여 작성하였지만, 이와 같은 풀이 시 시간초과 문제를 겪게 된다. 그 이후 고민을 해보다 보면 기본 피보나치를 활용한 문제로 풀면 앞에 함수에 count변수를 활용하듯이 시간초과 문제가 발생할 수밖에 없는 구조라는 것을 파악할 수 있다.

그 이후 언제 0 또는 1을 리턴을 할까?라는 고민을 하다 보면 n에 따라 피보나치 함수는 o과 1을 몇 번 출력하는지 규칙을 찾을 수 있게 된다.

 

n에 따라 0을 출력하는 횟수와 1을 출력하는 횟수가 피보나치 함수와 같이 

n = k-1인 경우와 n = k인 경우를 더하면 n = k+1 일 때 0과 1의 출력 횟수라는 사실을 알 수 있다.

 

 

 

그 이후 for문을 통해 0과 1을 출력하는 횟수를 arr에 저장해 나가며 풀이하였다.

 

│풀이 (C언어)

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

int main(void) {

    int t;

    int n;

    scanf("%d", &t);

    for (int i = 0; i < t; i++) {

        scanf("%d", &n);

        int num_0 = 1;

        int num_1 = 0;

        int tmp = 1;

        for (int j = 0; j < n; j++) {

            num_0 = num_1;

            num_1 = tmp;

            tmp = num_0 + num_1;

        }

        printf("%d %d\n", num_0, num_1);

    }

    return 0;

}

 

│설명  (C언어)

c언어에서의 특별한 설명은 없다. 문제에 관한 설명은 위의 파이썬 풀이 설명을 참고하기 바란다. 

c언어 풀이의 경우 파이썬과 다르게 배열에 불편함을 많이 겪기에 따로 배열에 저장하지 않고 n이 늘어날 때마다 

tmp변수를 활용하여 변수에 새로 값을 넣어주며 풀이하였다.