[백준 알고리즘/Python3] 1003, 피보나치 함수

Python3 코드

for i in range(int(input())):
    
    act_num = int(input())
    fibo_0 = [1,0]
    fibo_1 = [0,1]
 
    for i in range(2,act_num+1):
        fibo_0.append(fibo_0[i-1] + fibo_0[i-2])
        fibo_1.append(fibo_1[i-1] + fibo_1[i-2])
    
    if act_num == 0:
        print("%d %d"%(fibo_0[-2],fibo_1[-2]))
    else:
        print("%d %d"%(fibo_0[-1],fibo_1[-1]))

 

Python 코드 풀이

1. 첫째 줄에 테스트 케이스의 갯수를 받는다.

for i in range(int(input())):

input()을 int()로 캐스팅하고 바로 for문에 넣어준다.

 

 

2.  for문안에서 테스트를 할 수를 입력받는다.

act_num = int(input())

 

3. 피보나치 수열의 0의 갯수, 1의 갯수 규칙을 찾는다. 

0의 개수는 f(n-1)의 값과 같다.

1의 개수는 f(n)의 값과 같다.

 

fibo_0 = [1,0]
fibo_1 = [0,1]
 
    for i in range(2,act_num+1):
        fibo_0.append(fibo_0[i-1] + fibo_0[i-2])
        fibo_1.append(fibo_1[i-1] + fibo_1[i-2])

fibo_0은 0의 개수를 담는 리스트이다.

fibo_1은 1의 개수를 담는 리스트이다.

 

최소한 리스트의 0부터 돌 수 있게끔

0,1를 기본적으로 설정해준다.

 

피보나치 수열이 2부터 입력받은 수까지 for문을 돈다.

 

for문 안에서는

fibo_0, fibo_1에 리스트 원소의 -1,-2한 값을 더하고 리스트 맨 오른쪽에 넣는다.

 

ex) fibo_0에 4까지 피보나치 수열을 구한다면

[1,0,1,1,2]로 리스트의 맨 오른쪽 2 + 맨 오른쪽에서 1칸 왼쪽 = 피보나치 수 

 

위 과정은 입력받은 수까지 실행한다.

 

 

 

 

4. 입력받은 수가 0이라면

if act_num == 0:
	print("%d %d"%(fibo_0[-2],fibo_1[-2]))
else:
	print("%d %d"%(fibo_0[-1],fibo_1[-1]))

위 식의 예외사항이 있다.

만약 일반적인 식처럼 하면 0의 피보나치 수열의 리스트는 [0,1]이 될 것이다.

하지만 답은 [1,0]이여야 한다.

 

0일 때만 예외처리를 해준다.

리스트의 오른쪽에서 2번째 칸으로 지정해서 출력을 한다.

 

다른 수들은 리스트의 맨 오른쪽것을 출력해야 한다.

 

% 포맷으로 리스트의 값을 %d 에 준다.

 

 

 

마무리 

처음에 제귀함수로 하고 시간초과가 났다

 

그후 Dynamic Programing을 해봤지만 감을 찾지 못했다.

 

힌트를 살짝보고 0의 갯수, 1의 갯수에 규칙이 있다는걸 파악했다.

 

그것을 보고 프로그램을 작성 했지만 백준에서 틀렸다고 나왔다

 

함수형태를 지워버리고 바로 만들어서 통과를 했다.