| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.25 초 (추가 시간 없음) | 128 MB | 178128 | 51961 | 40757 | 31.963% |
문제
다음 소스는 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이 출력되는 횟수를 공백으로 구분해서 출력한다.
답안
import sys
count = [(1, 0), (0, 1)]
for i in range(2, 41):
count.append((count[i-2][0]+count[i-1][0], count[i-2][1]+count[i-1][1]))
t = int(sys.stdin.readline())
for _ in range(t):
zero_count, one_count = count[int(sys.stdin.readline())]
print(zero_count, one_count)풀이
문제에 주어진 n에 대응하는 0과 1의 개수는 아래와 같은 규칙을 가진다.
| n | 0의 개수 | 1의 개수 |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | 1 |
| 3 | 1 | 2 |
| 4 | 2 | 3 |
| 5 | 3 | 5 |
| 6 | 5 | 8 |
| 7 | 8 | 13 |
| i | 2칸 위 숫자 + 1칸 위 숫자 | 2칸 위 숫자 + 1칸 위 숫자 |
즉, 정리하면
- n이 0일 때 0과 1의 개수는 (1, 0),
- n이 1일 때 0과 1의 개수는 (1, 1)의 값을 가지며,
- n이 0과 1 이외의 값을 가질 때에는
- 0의 개수는 n-2에 대응하는 0의 개수 + n-1에 대응하는 0의 개수
- 1의 개수는 n-2에 대응하는 1의 개수 + n-1에 대응하는 1의 개수
를 가진다.
달리 말하면 0의 개수는 n=2부터, 1의 개수는 n=1부터 피보나치 수열을 형성한다고 볼 수도 있다.
따라서 n-2, n-1에 대응하는 0과 1의 개수를 기록하는 방법과, 피보나치 수열을 구한 뒤 알맞게 출력하는 방법이 있을 텐데(더 많은 방법이 있을 수 있다) 나는 그 중 전자를 택했다.
count = [(1, 0), (0, 1)]
for i in range(2, 41):
count.append((count[i-2][0]+count[i-1][0], count[i-2][1]+count[i-1][1]))count 리스트 안의 인덱스 i를 가지는 튜플은 n=i일 때 그에 대응하는 (0의 개수, 1의 개수)를 의미한다.
n=0일 때 (1, 0), n=1일 때 (0, 1)로 count를 초기화한 뒤, 규칙에 맞게 n의 최댓값인 40까지 count 리스트를 채운다.
zero_count, one_count = count[int(sys.stdin.readline())]
print(zero_count, one_count)count[n], 즉 n에 대응하는 (0의 개수, 1의 개수)를 출력 형식에 맞춰 출력한다.
이예찬