시간제한 : 0.25초(추가 시간 없음)
메모리 제한 : 128MB
다음 소스는 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)을 호출하면 다음과 같은 일이 일어난다.
1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
3
0
1
3
1 0
0 1
1 2
import sys
T = int(sys.stdin.readline().strip())
# fb(0) ~ fb(1)까지의 0의 개수
zeros = [1, 0]
# fb(0) ~ fb(1)까지의 1의 개수
ones = [0, 1]
# N이 40보다 작거나 같은 자연수이므로 fb(40)까지의 값을 저장
for i in range(2, 41):
zeros.append(zeros[i-1] + zeros[i-2])
ones.append(ones[i-1] + ones[i-2])
# fb(n)의 0과 1의 개수 출력
for _ in range(T):
n = int(sys.stdin.readline().strip())
print(zeros[n], end=' ')
print(ones[n])
시간 : 40ms
메모리 : 31256KB
이 문제는 DP
를 이용해 피보나치 수열의 0
과 1
의 수를 카운팅하면 된다.
피보나치 수열의 n
을 호출하면 n-1
+ n-2
을 return
한다.
따라서 n
을 호출했을 때 n-1의 0과 1의 개수
, n-2의 0과 1의 개수
를 합쳐서 return
해주면 된다는 뜻이다.
표로 설명하자면 아래와 같다.
n | 0 | 1 |
---|---|---|
0 | 1 | 0 |
1 | 0 | 1 |
2 | 1 | 1 |
3 | 1 | 2 |
4 | 2 | 3 |
... | ... | ... |
n
이 4
일때는 3(n-1)의 0과 1의 개수 [1, 2]
과 2(n-2)의 0과 1의 개수 [1, 1]
을 더해 [2, 3]
이 된다.
이걸 이용해 풀기 전에 fb(0)
과 fb(1)
일 때의 0
과 1
의 개수를 미리 정의해놓는다.
그 후 테스트 케이스의 n
들은 40보다 작거나 같은 자연수이므로 for문을 통해 2부터 40까지
의 0과 1의 개수
를 구해준다.
그러면 fb(0)
부터 fb(40)
까지의 0과 1의 개수
를 다 저장하게 된다.
그 후 n
에 맞게 그저 인덱싱해서 출력해주면 된다.