2502 떡 먹는 호랑이 / c++ / Silver1 / 14분
문제 및 코드
접근 방식
완전 탐색 (브루트 포스), 동적 프로그래밍
- 할머니는 항상 그저께와 어제 준 떡의 합만큼 오늘 호랑이게 떡을 주신다.
- 그렇다면 첫 날에 주신 떡의 개수를 A, 다음 날에 주신 떡의 개수를 B라고 가정해보자.
- 그러면 3일 째에는 A + B 개의 떡을 주시고
- 4일 째에는 A + 2B개, 5일 째에는 2A+3B개 주신다.
- 결국 D라는 날에 주신 떡의 개수는 피보나치 수열을 통해 알 수 있다.
- 하지만 주의해야 할 점은 A의 배수는 1,0,1 로 시작하고, B의 배수는 0,1 로 시작한다는 점이다.
- 그렇게 D날에 필요한 A의 배수와 B의 개수를 알았다면, 그걸 다시 A=1부터 시작해서 A=K까지 완전 탐색을 통해 적절한 값을 찾는다.
- 이 경우 만약 D가 7이라면, K=5A+8B를 만족해야하는데, K가 34이고, A가 2라고 가정한 경우
34 = 10 + 8B -> 8B = 24 -> B = 3 라는 적절한 값을 찾을 수 있다.
- 해결
다시 생각해 볼 점
- 나는 풀 때 A와 B의 배수를 각각 계산했지만, 사실 B는 피보나치 수열에서 A 바로 다음 값이다.
(3A+5B, 5A+8B, 8A+13B…)
(물론 1일,2일,3일 일 때에는 예외이다.)
