[백준] 1003번 문제 풀이: 파이썬(python) 코드 설명

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

1003번: 피보나치 함수

 

---

Hint

 

문제 예제에 있는 코드를 직접 작성하여

실행해보면

0이 출력된 횟수와

1이 출력된 횟수에 규칙이 있다

 

---

Solution

 

 

def fibonacci(n):
    if n==0:
        print(0)
        return 0
    elif n==1:
        print(1)
        return 1
    else:
        return fibonacci(n-1)+fibonacci(n-2)

문제에 있는 C++코드를

Python으로 옮겨보면 다음과 같이 표현할 수 있다

 

실제로 이대로 실행해보면

아래와 같은 결과를 얻을 수 있다

 

 

실제로 위 코드를 실행했을 때의 결과이다

0이 출력된 횟수를 보면 1, 0, 1, 1, 2, 3, 5, 8 이런 식으로

4번째부터 피보나치 수열처럼 나오고

1이 출력된 횟수를 보면 0, 1, 1, 2, 3, 5, 8, 13으로

3번째부터 피보나치 수열이 나오는 것을 알 수 있다

 

즉,  0이 출력되는 횟수와 1이 출력되는 횟수

각각 피보나치 수열을 이용하여 나타낼 수 있습니다

 

 

T=int(input())
for i in range(T):
    N=int(input())
    zero=[1,0,1]
    one=[0,1,1]
    if N >= 3:
        for i in range(3, N+1):
            zero.append(zero[i-1]+zero[i-2])
            one.append(one[i-1]+one[i-2])
    print(zero[N], one[N])

실제 정답이 나온 코드입니다

zero는 0이 출력되는 횟수를 list로 저장하고

one은 1이 출력되는 횟수를 list로 저장합니다

 

그리고 피보나치 수열의 규칙을 그대로 적용하면 됩니다