백준 알고리즘 | 1003 : 피보나치 함수 (Python / 파이썬)

---

피보나치 함수 성공분류

​

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
0.25 초 (추가 시간 없음)	128 MB	97840	24359	19231	29.771%

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

1003번: 피보나치 함수

---

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.

fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.

두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.

fibonacci(0)은 0을 출력하고, 0을 리턴한다.

fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.

첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.

fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

​

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

​

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

​

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

​

알고리즘 분류

다이나믹 프로그래밍

---

백준 알고리즘 # 1003번 : 피보나치 함수

t = int(input())

for i in range(t):
    n = int(input())
    zero = 1
    one = 0
    tmp = 0
    for _ in range(n):
        tmp = one
        one = one + zero
        zero = tmp
    print(zero, one)

풀이

문제에 주어진 n이 0일 경우 0 return과 n이 1일 경우 1 return하는 경우를 제외하고는

모든 정수 n은 fibonacci(n‐1) + fibonacci(n‐2)를 return한다.

​

이 규칙을 표로 만들면

n	0	1	2	3	4
zero	1	0	1	1	2
one	0	1	1	2	3

위와 같은 표가 만들어집니다.

​

여기에 예제 입력으로 주어진 n = 0, 1, 3을 대입한다고 생각하고 풀이를 하면

처음 테스트 케이스의 정수를 t로 입력받고 for문으로 t만큼 반복해줍니다.

​

여기서 n변수를 설정해서 정수를 입력받고

zero 변수를 설정해서 0이 출력되는 횟수를 알아보고 (n이 0일 때 zero가 한 번 출력되니 1로 초기화해두었습니다.)

one 변수를 설정해서 1이 출력되는 횟수를 알아봅니다.

그리고 tmp 변수를 설정해서 임시 저장할 공간을 만들어서 코드를 진행합니다.

​

for문으로 n으로 입력받은 정수만큼 반복을 해주고

tmp 임시저장소에 one의 값을 잠시 저장해두고

one은 one + zero 값을 더해준 값으로 초기화시킵니다.

마지막으로 zero는 잠시 저장해둔 tmp 값으로 초기화 시키면 끝!

​

예시로 n = 3이 실행되는 것을 보면 for문은 0, 1, 2 / 3번 돌아가니

tmp = 0

one = 0 + 1 = 1

zero = 0

​

tmp = 1

one = 1 + 0 = 1

zero = 1

​

tmp = 1

one = 1+ 1 = 2

zero = 1

​

마지막으로 zero, one 순으로 출력해주면 1 2가 나오면서 풀이 끄--읏!👏

(개인적으로 다이나믹 프로그래밍이 문제 이해는 쉬운데 코드로 입력하는게 어려운 것 같다..😂😂)

자세한 코드가 궁금하신 분들은 아래 GitHub 코드를 참고해주세요🙏

wook2124/Algorithm

최종 소스코드