2502 떡 먹는 호랑이

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

2502번: 떡 먹는 호랑이

---

사실 골드 문제를 풀다가 현타가 와서 실버 문제를 찾게 되었다... 열심히 해야겠다.

접근

호랑이에게 떡을 주는 방법은 어제 준 떡 갯수 + 그저께 준 떡 갯수이다.

 

피보나치와 똑같은데 문제는 첫 날과 둘째 날에 떡을 몇 개 줬는지 모르고, D번째 날에 K개 만큼 줬다고 한다.

 

어떤 공식으로 한 번에 풀리지 않을 것 같아 예시를 써보기로 했다.

 

첫 날에 준 떡 갯수를 $a$, 둘째 날에 준 떡 갯수를 $b$라고 하자.

1일: a
2일: b
3일: (a)+(b)
4일: (a+b)+(b)
5일: (a+b+b)+(a+b)
6일: (a+b+b+a+b)+(a+b+b)
...

5일에 준 떡 갯수를 세어보면 $2a+3b$이다. 

6일에 준 떡 갯수를 세어보면 $3a+5b$이다.

 

잘 보면 계수가 피보나치이다!

 

피보나치의 n번째 값을 f(n)이라고 할 때, K번째 날에 준 떡 갯수는 $K = af(D-1)  + bf(D-2)$이다.

 

이 문제가 dp인 이유는 피보나치를 활용했기 때문이고, $a$와 $b$의 값을 구하기 위해선 일일이 대입해봐야 한다.

 

문제에서 항상 답이 존재한다 했으므로 무한 반복 돌려서 찾아내면 된다. 못해도 1부터 K사이에 있으니까 괜찮다.

미흡했던 점

기하학문제를 풀다가 DP로 넘어오니 뇌가 초기화된 느낌이다. 더 풀어야 한다.

---

#include <iostream>
int dp[30]{0, 1}, A = 0, B = 0;
int main() {
  int D, K;
  for (int i = 2; i < 30; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  scanf("%d %d", &D, &K);
  for (int i = 1;; i++) {
    if ((K - dp[D - 2] * i) % dp[D - 1] == 0) {
      A = i;
      B = (K - dp[D - 2] * i) / dp[D - 1];
      break;
    }
  }
  printf("%d\n%d", A, B);
}