백준 1003 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.

해당 부분 지적 감사히 받습니다.

 

문제를 보자

피보나치 문제로, 일주일 전 백준을 처음 접했을 때 풀어보고 못 풀어 좌절했던 문제다.

 

처음엔 당연히 입력이 들어올 때마다 계산하도록 코드를 짰다.

 

코드

import sys as s

a = int(s.stdin.readline())

zero = 0

one = 0

def fibo(n):

    global zero,one    

    if n < 2 :

        if n == 0 :

           zero +=1

        else:

            one +=1

    else:

        fibo(n-1)

        fibo(n-2)

       

for i in range(a):

    fibo(int(s.stdin.readline()))

    print(zero,one, end='\n')

    zero, one =0,0

하지만 시간 초과 오류가 났고, 제한 시간을 확인해 보니 0.25초였다.

 

동적 프로그래밍이 바로 생각났고, 그냥 어떤 값이 들어오든 N의 범위가 40 아래이니 미리 계산해 두고 뽑기로 생각했다.

 

코드

a = int(input())

zero = 0

one = 0

zero_array, one_array = [1,0]*21,[0,1]*21

def fibo(n):

    global zero,one

    if n == 0 :

        zero += 1

        return

    if n == 1 :

        one += 1

        return

    else:

        zero_array[n]= int(zero_array[n-1]) + int(zero_array[n-2])

        one_array[n]=int(one_array[n-1]) + int(one_array[n-2])

       

for i in range(2,41):

    fibo(i)

    zero, one = 0,0

for i in range(a):

    b = int(input())

    print(zero_array[b],one_array[b],end='\n')

그리고 코드의 else 구문을 구현할 때,  또 하나  배운 점이 있다.

 

1. array [n] = array [n-1] + array [n-2]

2. array.append(array [n-1] + array [n-2])

 

두 가지 방법으로 구현했을 때, 아래 케이스가 8ms 더 빨랐다.

 

배운 점

1. 배열을 처음 선언할 때, 공간을 마땅히 할당해주지 않으면 당연히 참조도 안되고 값 삽입도 안된다.