[KOI] 백준 2502 - 떡 먹는 호랑이

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

힌트

첫날에 준 떡의 양을 $f_{1}$, 둘째 날에 준 떡의 양을 $f_{2}$라고 하자.

 

떡을 주는 규칙을 살펴보면 $f_{n} = f_{n - 1} + f_{n - 2}$으로 피보나치 수열과 같은 점화식이다.

 

조건을 만족하는 적절한 $f_{1}$과 $f_{2}$는 $O(DK \log K)$의 시간복잡도로 찾을 수 있다.

 

$f_{1}$가 정해져 있을 때 $f_{2}$를 찾는 방법을 생각한다.

풀이

선형 점화식 $f_{n} = f_{n - 1} + f_{n - 2}$로 계산한 $f_{d}$가 주어질 때 $f_{1}$과 $f_{2}$를 구하는 문제이다.

 

각 항에 대해 값을 1부터 $10^{5}$까지 무식하게 찾으면 시간복잡도 $O(K^{2})$가 되어 시간 초과를 받을 것이 뻔하다. (사실 이 문제에서 $O(N^{2} \log N)$이 통과하는 걸 생각하면 아닐 수도 있는데 시도해보진 않았다.)

 

아무튼 제곱 시간복잡도를 회피하는 방법을 생각해보자. 사실 이는 이진 탐색으로 찾을 수 있다.

 

$f_{1}$을 1부터 $10^{5}$까지 반복문을 돌면서 이진 탐색으로 답이 되는 $f_{2}$를 찾아주면 된다.

 

$f_{1}$이 답을 찾을 수 있는 적절한 값이라고 할 때 $f_{2}$가 너무 크면 $f_{d}$가 k보다 클 것이고 너무 작으면 k보다 작을 것이라는 것은 잘 알 수 있다.

 

위 아이디어를 따라 $f_{d} = k$가 되는 $f_{2}$를 찾으면 된다. 그런데 답을 찾을 수 있는 $f_{1}$을 모르므로 1부터 $10^{5}$까지 반복문을 돌며 iteration 마다 이진 탐색을 하자.

 

답이 존재하는 입력만 들어옴이 보장되므로 무조건 알맞은 답을 찾을 수 있다.

 

Overall Time Complexity : $O(DK \log K)$

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using pii = pair<int, int>;
using ll = long long;
 
int d, k;
ll dp[33];
 
void solve()
{
  cin >> d >> k;
 
  for (int i = 1; i <= 100000; i++)
  {
    int l = 1, r = 100000;
 
    while (l <= r)
    {
      int m = l + (r - l) / 2;
 
      dp[1] = i, dp[2] = m;
 
      for (int j = 3; j <= d; j++)
      {
        dp[j] = dp[j - 1] + dp[j - 2];
      }
 
      if (dp[d] > k)
      {
        r = m - 1;
      }
      else
      {
        if (dp[d] == k)
        {
          cout << dp[1] << '\n' << dp[2];
          return;
        }
        l = m + 1;
      }
    }
  }
  assert(false);
}
 
int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록