백준 2502. 떡 먹는 호랑이

https://www.acmicpc.net/problem/2502

2502번: 떡 먹는 호랑이

 

dp와 브루트포스를 쓴 문제.

 

마지막날인 D번째 날에 할머니가 호랑이에게 준 떡의 수 K가 주어진다. 

그리고 우리는 첫째날과 둘째날에 할머니가 준 떡의 수를 구해야 한다. 

 

호랑이는 피보나치 수열처럼 떡을 먹기 때문에 첫 번째날 준 떡의 수를 A 두 번째날 준 떡의 수를 B라고 하면 A와 B로 D번째 날 준 떡의 수를 표현할수 있다.

 

1 번째 날 : A

2 번째 날 : B

3 번째 날 : A+B

4 번째 날 : A + 2B

5 번째 날 : 2A + 3B 

6 번째 날 : 3A + 5B 

...

 

구하는건 dp로 피보나치 수열의 값 구하듯이 구하면 된다. 

 

이렇게 D번째 날을 A와 B로 표현하고 나면, 나머지는 브루트포스 방식으로 A에 값일 1부터 넣어보고, 그에 따른 B가 성립되면 답이다.