728x90
https://www.acmicpc.net/problem/1003
1003번: 피보나치 함수
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
www.acmicpc.net
import sys
t = int(sys.stdin.readline())
for _ in range(t):
a = int(sys.stdin.readline())
if a == 0:
print(1, 0)
continue
elif a == 1:
print(0, 1)
continue
arr = [[0] * 2 for _ in range(a + 1)]
arr[0] = [1, 0]
arr[1] = [0, 1]
for i in range(2, a + 1):
arr[i] = [arr[i - 2][0] + arr[i - 1][0], arr[i - 2][1] + arr[i - 1][1]]
print(arr[a][0], arr[a][1])
기본재귀함수를 사용하여 0과 1이 호출될 때마다 개수를 세어 출력하면 시간초과가 떠 다른 풀이를 생각해 보았다.
먼저 입력받은 값 a 가 0 또는 1 일 경우에는 출력을 해준다.
1보다 클 경우에는 arr 2차원 리스트를 선언하고 반복문을 통해 0이 나오는 횟수와 1이 나오는 횟수를 피보나치 수로 더해준다.
f(2) = f(1) + f(0) 이 식을 출력 횟수로 보면
[1,1] = [0,1]+[1,0] 으로 볼 수 있다.
728x90
'알고리즘 풀이 > 다이나믹 프로그래밍' 카테고리의 다른 글
[백준/파이썬] 1463번: 1로 만들기 (0) | 2023.01.10 |
---|---|
[백준/Python]1149번 : RGB거리 (0) | 2023.01.05 |
댓글