본문 바로가기
Algorithm Theory/Dynamic Programming

[DP] [BOJ 1003] 피보나치 함수

by hyeyoo 2020. 3. 22.
※ 이 블로그의 글은 글쓴이가 공부하면서 정리하여 쓴 글입니다.
※ 최대한 내용을 검토하면서 글을 쓰지만 틀린 내용이 있을 수 있습니다.
※ 만약 틀린 부분이 있다면 댓글로 알려주세요.

 

 

1003번: 피보나치 함수

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

www.acmicpc.net

문제

피보나치 함수의 변형 문제로, f(n)을 호출할 때, f(0)과 f(1)의 횟수를 각각 출력하는 문제 (f = 피보나치 함수)

 

해석

오늘은 태블릿을 놓고와서 그림은 없다.

 

이 문제는 처음에 알쏭달쏭하다. 내가 풀어봤던 피보나치 함수는 함숫값만 구하면 됐는데, 호출 횟수를 구하라니? 그리고 사실은 문제가 2개다. 0을 호출하는 횟수와 1을 호출하는 횟수. 그래서 두 문제를 한꺼번에 풀다 보니 헷갈리는 부분이 있다.

 

하지만 결국 푸는 방식은 완전히 동일하다. 피보나치 함수에서 f[n] = f[n-1] + f[n-2]라는 식으로 풀었던 것처럼,

(f(n)에서 f(0)을 호출하는 횟수) = (f(n-1)에서 f(0)을 호출하는 횟수) + (f(n-2)에서 f(0)을 호출하는 횟수)

(f(n)에서 f(1)을 호출하는 횟수) = (f(n-1)에서 f(1)을 호출하는 횟수) + (f(n-2)에서 f(1)을 호출하는 횟수)

가 성립한다. 왜냐? 그림을 그려보면 눈에 보인다. 무튼 간에, 따라서 피보나치 함수 문제와 같은 점화식으로 문제를 풀 수 있다. 단, 0, 1에 대해서 모두 정답을 구해야 하므로 배열이 2개 필요하다.

 

다시 정리하면, 다음과 같이 풀 수 있다.

zero : f(0)의 호출 횟수를 저장하는 배열, one : f(1)의 호출 횟수를 저장하는 배열

초기값 정하기 : 

zero[0] : f(0)은 f(0)을 1번 호출하므로 zero[0] = 1

zero[1] : f(1)은 f(0)을 0번 호출하므로 zero[1] = 0

one[0] : f(0)은 f(1)을 0번 호출하므로 zero[0] = 0

one[1] : f(1)은 f(1)을 1번 호출하므로 zero[1] = 1

 

점화식으로 풀기 : 

zero[n] = zero[n-1] + zero[n-2]

one[n] = one[n-1] + one[n-2]

 

구현

 

'Algorithm Theory > Dynamic Programming' 카테고리의 다른 글

[DP] [BOJ 2579] 계단 오르기  (0) 2020.03.30
[DP] [BOJ 2163] 초콜릿 자르기  (0) 2020.03.24
[DP] [BOJ 1149] RGB거리  (0) 2020.03.20
[DP] [BOJ 11726] 2 x n 타일링  (0) 2020.03.19
[DP] [BOJ 9095] 1, 2, 3 더하기  (0) 2020.03.18

댓글