BAEKJOON 1003

26 Jan 2020

문제

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

---

나의 처음 코드

저번 포스팅(2748)에서 다룬 피보나치 문제랑 별반 다를게 없다. 다만 이번에는, 계산할 때 사용된 0과 1의 갯수를 카운트 해서 구하라는 문제이다. 머릿속으로 5을 구할 때 필요한 0과 1의 갯수와 3과4를 구할 때 필요한 0과 1의 갯수를 따져보면 이 또한 피보나치 수열을 따르는 것을 볼 수 있다. 그 과정을 담은 코드는 다음과 같다.

n = int(input())
num_list = []
num_of_zero = [1,0,1]
num_of_one = [0,1,1]

def get_count(nth : int):
    global num_of_one
    global num_of_zero
    #원하는 값이 이미 구해져있다면 pass
    if len(num_of_one) >= nth + 1:
        pass
    else:
        for i in range(len(num_of_one), nth+1):
            num_of_one.append(num_of_one[i-1] + num_of_one[i-2])
            num_of_zero.append(num_of_zero[i-1] + num_of_zero[i-2])
      
#get_count를 통해 num_of_zero와 num_of_one의 갯수를 차례로 채우고, 다음에 input이 존재하면 같은 과정을
#반복 하지 못하게 해주는 작업
for i in range(n):
    num_list.append(int(input()))
    get_count(num_list[-1])
    
#정답 프린트
for i in num_list:
    print(num_of_zero[i], num_of_one[i])

결과는 맞았습니다. 저번 피보나치 포스팅 문제랑 다를게 없는 문제이다. 이 문제로는 아직까지 DP의 매력을 못 느낄 수도 있다! 허나 걱정 안해도 된다. 느므 믄타 :(