[BOJ] 1003. 피보나치 함수

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

1003번: 피보나치 함수

 

 

1. 해결방법

"""
1. 아이디어
- 피보나치 수열을 이용해서 1이 출력된 횟수와 0이 출력된 횟수를 카운트 한다.
- 카운트 된 횟수를 배열에 append해서 print

2. 시간복잡도
- O(40N) == O(N)
"""

처음에 zero는 1,0로 나열되고 one은 0,1로 나열된다.
그 이후의 n번째부터는 피보나치 수열(N2 = N1 + N0)로 나열된다.

그렇다면 이제, 규칙을 가지고 구현해보자.

• 0과 1의 초기배열을 먼저 만들어준다.
• 0은 [1,0] 1은 [0,1] 로 정해져있음.
• for문으로 초기배열 이후 피보나치 수열로 구한 값을 배열에 추가해준다.
• 각 테스트케이스마다 0과 1의 횟수를 공백으로 출력해야한다.

 

2. 정답코드

import sys
input = sys.stdin.readline

N = int(input())


def fibo(num):
    for i in range(2, num + 1):
        zero.append(zero[i - 1] + zero[i - 2])
        one.append(one[i - 1] + one[i - 2])

    print(zero[num], one[num])


for i in range(N):
    num = int(input())
    zero, one = [1, 0], [0, 1]

    fibo(num)

DP가 익숙하지 않은 사람이라면 해결하는데 좀 고민했을 것이다. 본인처럼,,,
그래도 못풀 문제는 아니니까 DP문제에 대한 이해와 피보나치 수열에 대한 이해만 조금 있으면 풀 수 있는 문제이다.