Challenge
문제를 요약하면 주어진 0 ~ 40 사이의 자연수 N이 주어지고, 피보나치 함수에서 0과 1이 출력되는 총 개수를 출력하는 문제입니다.
Description
다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.
int fibonacci(int n) {
if (n == 0) {
printf("0");
return 0;
} else if (n == 1) {
printf("1");
return 1;
} else {
return fibonacci(n‐1) + fibonacci(n‐2);
}
}
C++
복사
fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.
•
fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
•
fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
•
두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
•
fibonacci(0)은 0을 출력하고, 0을 리턴한다.
•
fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
•
첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
•
fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.
1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.
Inputs
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.
* Examples 1
3
0
1
3
* Examples 2
2
6
22
Plain Text
복사
Outputs
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
* Examples 1
1 0
0 1
1 2
* Examples 2
5 8
10946 17711
Plain Text
복사
Solve
풀이로 요구하는 내용은, 피보나치 수열을 알아내는 함수의 원리와 Dynamic Programming 방법을 이용하여 적절한 값을 빠르게 알아내는 문제입니다.
Python
def add_list(first, second):
res = []
res.append(first[0] + second[0])
res.append(first[1] + second[1])
return res
def fibonacci(num):
answer = [[1,0], [0,1]]
if num == 0:
return answer[0]
elif num == 1:
return answer[1]
else:
for __ in range(num-1):
answer.append(add_list(answer[-1], answer[-2]))
return answer[-1]
if __name__ == "__main__":
answers = []
for _ in range(int(input())):
answers.append(fibonacci(int(input())))
for a in answers:
print(f"{a[0]} {a[1]}")
Python
복사
Reviews
문제를 풀 때 피보나치 수열에 대한 이해는 있었습니다. 하지만 주어진 피보나치 함수로 원하는 값을 구하게 되면 모든 경우의 수를 검사하기 때문에 비효율적입니다. 때문에 피보나치 수열에서 힌트를 얻어 문제를 풀어보았습니다. 머리로만 생각하다가 공책으로 쓰면서 풀어보니까 더 잘 풀리는 듯합니다.
