문제
문제 링크
다음 소스는 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);
}
}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이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.
출력
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
Code
import sys
input = sys.stdin.readline
test_case = int(input().rstrip())
list_ = []
for i in range(41) :
if i == 0 :
list_.append([1, 0])
elif i == 1 :
list_.append([0, 1])
else :
list_.append([list_[i-2][0] + list_[i-1][0], list_[i-2][1] + list_[i-1][1]])
for _ in range(test_case) :
N = int(input().rstrip())
print(list_[N][0], list_[N][1]) 코드 설명
처음에는 문제에 제시된 피보나치 수열 함수를 사용하려고 했는데, 풀다보니 그렇게 푸는 게 더 어려운 것 같아서 그냥 피보나치의 원리를 이용하기만 했다.
import sys
input = sys.stdin.readline
test_case = int(input().rstrip())
list_ = []
빠른 입력을 받을 수 있도록 input을 선언하고 테스트 케이스의 개수를 받고 빈 리스트를 생성한다.
for i in range(41) :
if i == 0 :
list_.append([1, 0])
elif i == 1 :
list_.append([0, 1])
else :
list_.append([list_[i-2][0] + list_[i-1][0], list_[i-2][1] + list_[i-1][1]])
for _ in range(test_case) :
N = int(input().rstrip())
print(list_[N][0], list_[N][1]) 문제에서 N이 40 이하로만 주어진다고 했으므로 범위를 41으로 한 for문을 돌린다. 0번 인덱스부터 사용하기 때문에 41까지 돌려야 한다. 0과 1일 경우만 예외로 미리 지정해 두고, 그 이상은 i-1번 값과 i-2번 값을 더하는 식으로 저장한다. 이후 테스트 케이스만큼 for문을 돌려서 들어오는 숫자와 같은 인덱스에 위치한 값을 뽑아낸다.
리뷰
처음에 계속 문제에 주어진 함수를 사용하려고 해서 꽤 오래 걸렸다. 함수를 사용하지 않고 원리만 이용하자는 생각을 한 뒤로는 오래 안 걸린 것 같다.
