2502 떡 먹는 호랑이

2502 떡 먹는 호랑이 / c++ / Silver1 / 14분

문제 및 코드

접근 방식

완전 탐색 (브루트 포스), 동적 프로그래밍

1. 할머니는 항상 그저께와 어제 준 떡의 합만큼 오늘 호랑이게 떡을 주신다.
2. 그렇다면 첫 날에 주신 떡의 개수를 A, 다음 날에 주신 떡의 개수를 B라고 가정해보자.
3. 그러면 3일 째에는 A + B 개의 떡을 주시고
4. 4일 째에는 A + 2B개, 5일 째에는 2A+3B개 주신다.
5. 결국 D라는 날에 주신 떡의 개수는 피보나치 수열을 통해 알 수 있다.
6. 하지만 주의해야 할 점은 A의 배수는 1,0,1 로 시작하고, B의 배수는 0,1 로 시작한다는 점이다.
7. 그렇게 D날에 필요한 A의 배수와 B의 개수를 알았다면, 그걸 다시 A=1부터 시작해서 A=K까지 완전 탐색을 통해 적절한 값을 찾는다.
8. 이 경우 만약 D가 7이라면, K=5A+8B를 만족해야하는데, K가 34이고, A가 2라고 가정한 경우 34 = 10 + 8B -> 8B = 24 -> B = 3 라는 적절한 값을 찾을 수 있다.
9. 해결

다시 생각해 볼 점

1. 나는 풀 때 A와 B의 배수를 각각 계산했지만, 사실 B는 피보나치 수열에서 A 바로 다음 값이다. (3A+5B, 5A+8B, 8A+13B…) (물론 1일,2일,3일 일 때에는 예외이다.)