2520_떡 먹는 호랑이

[다시 풀었어도 난해한 문제]

오랜만에 드디어 문제가 풀렸다. ㅜㅜ

답이 잘 안 나오는 문제가 너무 많다. 분발하자. 

떡 먹는 호랑이 문제는 내가 너무 어렵게 생각한 거 같다. 

알고 봤더니 쉽고 정말 좋은 문제였다.라고 스스로 평가하고 싶다. 

우선 첫날 준 떡 + 두번째 날 준 떡 = 세번째 날 준떡 이어야 한다는 것은 피보나치 점화식을 가진다는 것을 알 수 있음!

문제에서는 n번째 날에 k의 떡을 준 것을 토대로 문제를 풀어 첫 번째 날과 두 번째 날에 준 떡의 개수를 알아내야 한다. 

처음은 점화식의

f(n) = a*f(n-2) + b*f(n-1) 이라는 식을 세워서 계수를 알아내야 한다고 생각 한다. 물론 맞다.

a와 b를 빼놓고 생각해본다면

f(n) = f(n-2) + f(n-1)이라는 점화식이 나오고

f(1) = 1, f(2) = 1로 놓으면 계수가 나오지 않겠는가!!!

결국 첫날 준 떡 a , 두번째 날 준 떡 b의 계수를 구할 수 있게 된다. 

이 계수를 토대로 a와 b를 구해야 한다. 어떻게?

처음은 다이나믹 프로그래밍으로 풀어야 하나를 생각해보면서 이상한 고민을 했었다. 

하지만 단지 이중 for문을 돌면서 때려 맞추고 break으로 빠져나오면 된다.

심각한 루프를 돌지도 않고 또한 워낙 범위가 많지 않아 무리 없이 수행 할 수 있다.!!!

문제의 조건들을 면밀히 살펴 시간분석도를 대략적으로 계산할 줄 알아야 한다는 생각을 했다. 이 부분을  좀 더 공부해야겠다.