1. 문제와 예제
(문제 링크: https://www.acmicpc.net/problem/1003)
2. 전체 코드
1) 피보나치 함수 원리 그대로 적용 (시간 초과 오류 발생)
# 시간 초과
import sys
input = sys.stdin.readline
# 입력 받기
T = int(input().rstrip()) # 테스트 케이스 개수
dct = {}
# 피보나치 함수
def fibonacci(n):
if (n == 0):
dct[0] += 1
return 0
elif (n == 1):
dct[1] += 1
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
for _ in range(T):
fibonacci(int(input().rstrip()))
print(dct[0], dct[1]) # 결과 출력
처음 생각나는 방법은 문제에서 준 피보나치 함수를 이용해서 구현하는 것이지만 시간 초과 오류가 나는 것을 확인할 수 있다.
2) 다이나믹 프로그래밍
import sys
input = sys.stdin.readline
# 입력 받기
T = int(input().rstrip())
zero = [1, 0, 1] # 0의 개수 리스트
one = [0, 1, 1] # 1의 개수 리스트
for _ in range(T):
N = int(input().rstrip()) # N번째 피보나치
while (N >= len(zero)):
zero.append(zero[-1] + zero[-2])
one.append(one[-1] + one[-2])
print(zero[N], one[N])
3. 코드 해설
시간 초과가 생기지 않도록 하려면 어떻게 해야할까 고민하는 과정에서 문제에서는 0과 1이 몇 번 출력되는지만 물어보는 것을 발견했다. 따라서 fibonacci(n)이 fibonacci(n-1)+fibonacci(n-2)로 쪼개진다는 점을 활용해 다이나믹 프로그래밍 방법을 이용했다.
'백준' 카테고리의 다른 글
[백준] 9375번 파이썬 (패션왕 신해빈) (0) | 2024.03.29 |
---|---|
[백준] 9095번 파이썬 (1, 2, 3 더하기) (0) | 2024.03.24 |
[백준] 17219번 파이썬 (비밀번호 찾기) (0) | 2024.03.23 |
[백준] 11399번 파이썬 (ATM) (4) | 2024.03.22 |
[백준] 11047번 파이썬 (동전 0) (0) | 2024.03.22 |