코딩테스트/백준
[백준] 1003번 피보나치 함수 / 파이썬(python)
Jiwon_C
2021. 3. 14. 21:15
# 문제 링크
1003번: 피보나치 함수
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
www.acmicpc.net
# 관련 알고리즘 이론
동적 계획법 (다이나믹 프로그래밍, DP)
# 동적 계획법 (Dynamic Programming) - Recursive + Memorization - 점화식 찾기! -> 작은 문제의 해를 테이블에 저장한 뒤, 나중에 읽어서 사용 - 상향식 (작은 -> 큰) 하향식 (분할 정복) - 대표적인..
jiwon-coding.tistory.com
# Soultion(실패)
재귀를 이용하여 문제를 풀었으나, 시간이 초과하는 문제 발생
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
cnt_0 = 0
cnt_1 = 0
def fibo(n):
# 전역변수
global cnt_0
global cnt_1
if n==0:
cnt_0 +=1
return 0
elif n==1:
cnt_1 +=1
return 1
else:
return fibo(n-1)+fibo(n-2)
t = int(input())
for _ in range(t):
n = int(input())
fibo(n)
print(cnt_0, cnt_1)
cnt_0 = 0; cnt_1 = 0
|
cs |
1. 2. 0과 1이 출력된 갯수 파악을 위한 전역변수
4. 피보나치 함수 생성, 함수안에서 각각 0과 1을 출력하게되면 카운팅
# Soultion(성공)
시간초과 문제를 해결하기 위해, 0과 1의 규칙을 찾아서 문제해결
0의 갯수 = 이전 1의 갯수, 1의 갯수 = 이전 0+이전1 갯수
|
1
2
3
4
5
6
7
8
9
10
11
12
|
t = int(input())
for _ in range(t):
cnt_0 = [1,0]
cnt_1 = [0,1]
n = int(input())
if n>1:
for i in range(n-1):
cnt_0.append(cnt_1[-1])
cnt_1.append(cnt_0[-2]+cnt_1[-1])
print(cnt_0[n], cnt_1[n])
|
cs |
4. 5. 기본으로 0과 1일때 갯수를 초기화시키기
7. 0과 1인 경우는 이미 리스트에 있으므로 1보다 클 경우만 진행
9. 현재 0의 갯수는 이전 1의 갯수를 가져옴
10. 현재 1의 갯수는 이전 0의 갯수+이전 1의 갯수