[백준] 1003번 : 피보나치 함수 (파이썬)

문제



나의 답안

t=int(input())

for i in range(t):
    arr0=[1,0]#n이 0인 경우
    arr1=[0,1]#n이 1인 경우
    n=int(input())
    if n>1:#n이 0과 1이 아닌경우
        for j in range(n-1):
            arr0.append(arr1[-1])#0의 개수: 직전 숫자의 1의 개수
            arr1.append(arr0[-2]+arr1[-1])#1의 개수: 직전 숫자의 1의 개수+0의 개수
    print(arr0[n],arr1[n])#n에 대한 0과 1의 개수에 대한 값 출력

접근 방법

NUMBER0123
ZERO1011
ONE0112
  • ONE: fibonacci(1) 이 몇 번 호출되는가
    ZERO: fibonacci(0) 이 몇 번 호출되는가

  • 문제의 조건에서
    fibonacci(1)은 1을 출력하고 1을 리턴한다.
    fibonacci(0)은 0을 출력하고, 0을 리턴한다.
    fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
    fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
    라고 하였으므로 위의 표와 같은 결과가 나온다.

  • 여기서, 0의 개수와 1의 개수에 대해 다음과 같은 규칙을 찾을 수 있다.

    NUMBER의 0의 개수 == (NUMBER-1)의 1의 개수
    NUMBER의 1의 개수 == ((NUMBER-1)의 1의 개수) + ((NUMBER-1)의 0의 개수)

따라서 위와같이 코드를 짜주면 된다.

좋은 웹페이지 즐겨찾기