[백준 1003] 피보나치 함수

문제

피보나치 함수를 실행했을 때 0일 때와 1일 때 몇 번 실행되는지 구하라

 

입력

첫째 줄에 테스트 케이스가 주어지며

이어서 40이하의 수가 입력된다.

 

출력

테스트 케이스마다 0일 때와 1일 때 실행횟수를 공백을 두고 출력한다.

---

접근

처음에 재귀함수를 사용해서 풀었는데 시간초과가 발생했다. 그래서 DP에 분류가 되어있던 것 같다

DP로 접근을 했을 때 각 수에서 0과 1이 몇 번실행되는지 규칙을 찾았을 때 현재인덱스 idx에서 idx-1, idx-2의 0과 1을 누적합을 해주면 된다.

 

구현

테스트 케이스마다 수를 입력받고 dp를 저장할 2차원 리스트를 생성한다.

그리고 초기에 0과 1에서는 0과 1이 몇 번 실행되는지 저장해둔다.

    N = int(input())
    dp = [[0, 0] for _ in range(41)]
    dp[0][0] = 1
    dp[0][1] = 0
    dp[1][0] = 0
    dp[1][1] = 1

 

만약 입려된 정수 N이 1이하라면 바로 저장된 수를 출력하며 2이상의 수는 for문으로 누적합을 구하도록 한다.

    if N <= 1:
        print(dp[N][0], dp[N][1])
    else:
        for idx in range(2, N+1):
            dp[idx][0] = dp[idx-1][0] + dp[idx-2][0]
            dp[idx][1] = dp[idx-1][1] + dp[idx-2][1]
        print(dp[N][0], dp[N][1])

---

전체 코드

T = int(input())
for tc in range(T):
    N = int(input())
    dp = [[0, 0] for _ in range(41)]
    dp[0][0] = 1
    dp[0][1] = 0
    dp[1][0] = 0
    dp[1][1] = 1
    if N <= 1:
        print(dp[N][0], dp[N][1])
    else:
        for idx in range(2, N+1):
            dp[idx][0] = dp[idx-1][0] + dp[idx-2][0]
            dp[idx][1] = dp[idx-1][1] + dp[idx-2][1]
        print(dp[N][0], dp[N][1])