백준 28127 - 숫자탑과 쿼리 (C++)

문제

• 문제 링크

  
   BOJ 28127 - 숫자탑과 쿼리 
  

• 문제 요약

$Q$개의 쿼리가 주어진다.
쿼리마다 탑을 쌓는 규칙이 함께 주어질 때, $x$가 적힌 숫자 블록이 몇 번째 층의 몇 번째 숫자인지 구해보자.

• 제한

TL : $2$ sec, ML : $1024$ MB




$1 ≤ Q ≤ 500,000$

$1 ≤ a, d, x ≤ 1,000,000$

알고리즘 분류

• 수학(math)
• 이분 탐색(binary_search)

풀이

쿼리마다 탑의 모양이 바뀐다.
즉, 주어지는 변수 $a, d$에 대해 일반화를 시켜야 한다.

$A_i$를 $i$번째 층의 제일 왼 쪽에 있는 수라고 정의한 후 초항을 나열해보면,

• $A_1 = 1$
• $A_2 = 1 + (a + d * 0)$
• $A_3 = 1 + (a + d * 0) + (a + d * 1)$
• $A_4 = 1 + (a + d * 0) + (a + d * 1) + (a + d * 2)$

위처럼 진행될 것이다.
이를 바탕으로 일반항 $A_n$을 정리해보면,

• $a$는 $n - 1$ 번 더해진다.
• $d$는 $1$ $+$ $2$ $+$ $...$ $+$ $n - 2$ 번 더해진다.

$A_n = 1 + a * (n - 1) + d * {(n - 1) * (n - 2) \over 2}$

---

$1 ≤ Q ≤ 500,000$ 이므로, $A_1, A_2, ... A_n$에 대해 $x$가 속한 층 수를 빠르게 구해야 한다.
모든 수가 양수임에 따라, 수열 $A_n$은 단조 증가한다.

따라서 $A_n$에 이분 탐색을 적용해볼 수 있다.

$Decision$ $Problem$ : 현재 구간 $[s, e]$에서, $x$가 ${s + e \over 2}$층보다 높거나 같은 층에 존재 하는가 ?

위에서 정리했던 식을 이용하면, 매 $Decision$ $Problem$를 $O(1)$에 풀 수 있으므로 전체 문제를 $O(QlogN)$에 해결할 수 있게 된다.

전체 코드

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll q; cin >> q;
    for (ll a, d, x, i, j; q--;)
    {
        cin >> a >> d >> x;
        for (ll s(1), e(1e6); s <= e;)
        {
            ll mid(s + e >> 1);
            ll Am(1 + a * (mid - 1) + d * (mid - 1) * (mid - 2) / 2);
 
            if (Am <= x) s = (i = mid) + 1, j = Am;
            else e = mid - 1;
        }
        cout << i << ' ' << x - j + 1 << '\n';
    }
}

comment

끝