[코테]99클럽 코테 스터디 36일차 TIL 백준 1003 피보나치 함수

일주일 동안 정신없이 면접보고.. 준비하고.. 하느라 한동안 코딩테스트를 못풀었다 ㅠ 

좋은 결과가 나왔으면 좋겠는데.. 잘모르겠다 ㅠㅠ 

어쨌든, 이 문제는 대표적인 DP문제이다. DP문제란, 분할정복과 비슷한 개념인데, 작은 것을 더해서 큰 것을 구한다? 느낌이다. 점화식이라고 보면 될것 같다. 

나는 DP문제를 한번도 풀어본적이 없어서 처음에는 문제 그대로 피보나치 함수를 짜서 카운트만 해봤는데 시간초과로 실패했다. 다음은 실패한 코드. 

import sys

read = sys.stdin.readline

T = int(read())

 

def fibonacci(n):

    global zero_cnt, one_cnt

    if n == 0:

        zero_cnt += 1

        return 0

    elif n == 1:

        one_cnt += 1

        return 1

    else:

        return fibonacci(n - 1) + fibonacci(n - 2)

 

for _ in range(T):

    N = int(read())

    zero_cnt = 0

    one_cnt = 0

    fibonacci(N)

    print(zero_cnt, one_cnt)

 

피보나치 함수 값만 더해서 나오는게 아니라, 1과 0의 호출 횟수도 점화식으로 나올 수 있다는 것이 이 문제의 포인트이다. 

import sys

read = sys.stdin.readline

T = int(read())

# N의 최대 입력값이 40 이므로 미리 설정

dp = [(0,0)] * 41

dp[0] = (1,0)

dp[1] = (0,1)

for i in range(2, 41):

    dp0 = dp[i - 1][0] + dp[i - 2][0]

    dp1 = dp[i - 1][1] + dp[i - 2][1]

    dp[i] = (dp0, dp1)

for _ in range(T):

    N = int(read())

    print(dp[N][0], dp[N][1])