https://www.acmicpc.net/problem/1003
1003번: 피보나치 함수
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 0을 호출하는 횟수, 1을 호출하는 횟수에 관한 것입니다. dp는 우선 n에 따른 결괏값을 나열한 뒤 규칙성을 파악하는 것이 가장 중요합니다. 따라서 n에 따른 규칙성을 파악해 보겠습니다. N의 값에 따른 0이 출력되는 횟수, 1이 출력되는 수를 표로 정리하면 다음과 같습니다.
4를 예시로 들어보면 다음의 그림과 같습니다.
위의 그림과 표에서 볼 수 있듯 fibonacci(4) 는 0을 2회 출력, 1을 3회 출력하는 것을 확인할 수 있다.
위의 표를 잘 살펴 보면 N >= 2일 때의 0, 1의 출력 횟수는 각각 N-1, N-2의 0, 1의 출력 횟수의 합인 것을 알 수 있다.
즉 이러한 규칙성을 가지고 문제를 해결하면 다음과 같다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
tc = int(input())
data = []
for i in range(tc):
data.append(int(input()))
zeroCount = [1, 0]
oneCount = [0, 1]
for i in range(2, 41):
zeroCount.append(zeroCount[i-1] + zeroCount[i-2])
oneCount.append(oneCount[i-1] + oneCount[i-2])
for i in range(tc):
print(zeroCount[data[i]], oneCount[data[i]])
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 11053번: 가장 긴 증가하는 부분 수열(Python) (0) | 2022.01.20 |
|---|---|
| 백준 알고리즘 2579번: 계단 오르기(Python) (0) | 2022.01.19 |
| 백준 알고리즘 7569번: 토마토(Python) (0) | 2022.01.15 |
| 백준 알고리즘 10026번: 적록색약(Python) (0) | 2022.01.15 |
| 백준 알고리즘 4963번: 섬의 개수(Python) (0) | 2022.01.15 |