두두두둥
→문제입니당←
문제
문제는 우리가 흔히 아는 피보나치인데 거기에 약간의 응용을 곁들인,,,
문제에서 재귀를 이용해서 짠 피보나치 코드를 준다.
재귀로 피보나치를 풀면 함수 f(n)은 f(n-1) f(n-2)를 호출한다.
예를 들면 f(4) = f(3) + f(2) -> f(3) = f(2) + f(1), f(2) = f(1) + f(0)
요런식으로 재귀에 재귀에 호출이 되는 형식이다.
그러면 여기서 최종적으로 f(1)이랑 f(0)이 몇번이나 호출되냐??
이게 핵심입니당..
근데 이거 그냥 공책에 흐름 생각하면서 풀어보니까 규칙이 있었슴다.
n = i 일때 0이 나오는 횟수 dp테이블을 dp_0[]
n = i 일때 1이 나오는 횟수 dp테이블을 dp_1[]
이라 했을 때,
dp_0은 1 0 1 1 2 3 5 8 ····
dp_1은 0 1 1 2 3 5 8 13 ····
요런 형식이다.
또보나치 수열이다.
맨 앞 두개의 원소만 따로 정의해주고 피보나치를 dp 풀듯이 코드 짜주면 끝이당
코드를 봅시다잉
def dp0(n):
dp=[1,0]
for i in range(2, n+1):
dp.append(dp[i-2]+dp[i-1])
return dp[n]
def dp1(n):
dp=[0,1]
for i in range(2, n+1):
dp.append(dp[i-2]+dp[i-1])
return dp[n]
ans = []
n = int(input())
for i in range(n):
m = int(input())
a = dp0(m)
b = dp1(m)
ans.append((a,b))
for i in range(n):
print("{0:d} {1:d}".format(ans[i][0], ans[i][1]))dp0, dp1 함수를 만들어 0, 1 따로 횟수 계산했다.
각각의 함수에 보면 초기 값을 [1,0], [0,1] 로 설정해 주고 뒤에는 쭉 피보나치로 돌린 걸 볼 수 있다.
맨 처음 생각만 잘하면 빠르게 풀 수 있는 문제였다.
Review
짱 근무 설 때 시간 때우기 용으로 문제를 풀어보고 있었는데 이 문제 푸는 데 5분도 안걸려서 기분 좋게 스트릭 채웠다. 피보나치는 DP나 재귀로 풀 수 있는데 워낙 유명해서 dp로 푸는 거는 그냥 사칙 연산 맹키로 기억에 저장되어 있었다. 그래서 그냥 슈슉 풀어버렸당. 이거 시작하고 처음으로 한번만에 맞췄다! 처음은 아닐수도 있다.
그리고 푼 날짜 제목에 적을려고 했는데 좀 오래 지난거는 언제 풀었는지 기억이 안나서 이제 날짜는 안적을 거 같다. 그리고 백준에는 문제마다 언제 풀었는 지 로그 안남음 ㅜㅜ
