📝 문제 설명
> 피보나치 수는 첫째항과 둘째항은 1이고, 그 이후부터는 바로 전 항 + 바로 전전 항 이 각각 오는 그런 수열이다.
1,1,2,3,5,8,13, ... 이런식으로 전개된다. 필요에 따라 0번째 항을 0이라고 부르기도 한다. 편하게 계산할 때!
출처 | https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98
이런 피보나치 수를 구하면 되는 문제다. 정확하게는 n이 주어지면, 그 0과 1을 각각 구하면 된다.
(여기서 0은 fibo(0)을 더해준 횟수와 같고, 1은 fibo(1)을 더해준 횟수와 같다)
[예시]
n = 4 일 때,
fibo(4) = fibo(3) + fibo(2)
fibo(2) + fibo(1) + fibo(2)
fibo(1) + fibo(0) + fibo(1) + fibo(1) + fibo(0)
결과 : 2 3
-> fibo(0)이 2개, fibo(1)이 3개라서 정답은 2 3 이 된다.
이는 fibo(3)의 0 과 fibo(2)의 0을 더한 결과 & fibo(3)의 1과 fibo(2)의 1을 더한 결과와 같다.
fibo(3)_0 개수 : 1, fibo(2)_0 개수 : 1 => 1 + 1 = 2
fibo(3)_1 개수 : 2, fibo(2)_1 개수 : 1 => 2 + 1 = 3
https://www.acmicpc.net/problem/1003
🎨 풀이
💡 전체 코드
def fibo(n):
length = len(zero)
if length <= n :
for i in range(length,n+1):
zero.append(zero[i-1]+zero[i-2])
one.append(one[i-1]+one[i-2])
print(zero[n], one[n])
zero = [1,0,1]
one = [0,1,1]
T = int(input())
for _ in range(T):
n = int(input())
fibo(n)
> 핵심 : 앞 순서의 시간이 뒤에 영향을 주니까, 수가 작은 순서대로 정렬한 후 누적해서 더해주면 된다!
🍦 코드 설명 (실행 순서대로 나열)
# main
zero = [1,0,1]
one = [0,1,1]
T = int(input())
for _ in range(T):
n = int(input())
fibo(n)
1. zero = [1,0,1], one = [0,1,1]
- zero : 0 개수 (순서대로 추가될 예정)
- one : 1 개수 (순서대로 추가될 예정)
- 0, 1, 2 까지만 미리 넣어져있고 그 후부터는 차례대로 추가될 예정임.
2. T를 입력받는다.
- T : 테스트 케이스 개수
@ for문 (3번~5번)
3. for문을 돌린다. (T만큼)
4. n을 입력받는다.
5. fibo(n) 함수를 실행시킨다.
# fibo(n)
def fibo(n):
length = len(zero)
if length <= n :
for i in range(length,n+1):
zero.append(zero[i-1]+zero[i-2])
one.append(one[i-1]+one[i-2])
print(zero[n], one[n])
6. length 변수에 zero 길이를 넣는다.
7. length와 n을 비교한다.
8-1. 만약 length가 n보다 크다면, 적어도 n 까지는 다 추가가 되어있다는 뜻이기 때문에 for문을 돌리지 않고 바로 출력한다.
8-2. length가 n보다 작다면, 추가를 해야한다는 뜻이기 때문에 for문을 실행한다.
@ for문 (9번~11번) => 추가해주는 작업
9. for문을 돌린다. (length부터 n까지)
10. zero에 zero[i-1] + zero[i-2] 값을 추가해준다.
11. one에 one[i-1] + one[i-2] 값을 추가해준다.
12. zero[n]와 one[n]을 출력한다.
끝~
⭐ 느낀점
> 열심히 적긴 했는데 이해가 잘 될랑가 모르겠다! 까먹을 때 쯤에 나중에 와서 한 번 더 봐야겠다. ^ㅁ^ 굿굿
'알고리즘 공부 > 백준' 카테고리의 다른 글
[백준] 1026번 - 보물 (파이썬) (0) | 2022.07.25 |
---|---|
[백준] 11047번 - 동전 0 (파이썬) (0) | 2022.07.24 |
[백준] 11399번 - ATM (파이썬) (0) | 2022.07.22 |
[백준] 2839번 - 설탕 배달 (파이썬) (0) | 2022.07.21 |
[DAY 100_백준] 1929번 - 소수 구하기 (파이썬) (0) | 2022.06.30 |