백준 28127 숫자탑과 쿼리

단순히 등차수열을 이용해서 푸는 문제인가 했는데, 시간복잡도를 좀 더 생각해서 접근해야 되는 문제였다.
정답은 맞췄는데 시간이 상당히 오래 걸렸다. 더욱 효율성있게 풀 수 있는 방법이 존재하는 것 같다.

📜 문제 바로 가기 : 숫자탑과 쿼리

제출 코드

import sys
input = sys.stdin.readline

def binarySearch(x):
   s, e = 1, x
   
   while 1:
       mid = (s+e) //2
       if ap(mid-1) < x <= ap(mid):
           return mid
       
       if ap(mid) < x:
           s = mid + 1
       else:
           e = mid - 1

def ap(x): # 등차수열 합공식
   return x * (2*a + (x -1) * d) // 2

Q = int(input())
for _ in range(Q):
   a, d, x = map(int, input().split())
   
   # 층 수 찾기
   layer = binarySearch(x)
   
   # layer 층의 블럭수
   block_count = (layer -1) * d + a

   # layer 층의 마지막 번호 : e
   e = ap(layer)

   # x 의 위치
   pos = block_count - (e - x)

   print(layer, pos)

---

접근 방법

등차수열의 합 공식을 이용하여 x 가 있는 탑의 층수를 구한다. 블럭은 매층 마다 공차 d 만큼 증가하기 때문에 등차수열의 합공식을 이용하면 특정 층의 마지막 블럭번호를 구할 수 있다. 결국 매층 마지막 번호를 알고 있으므로 x가 있는 층 수를 구할수가 있게 된다.

그리고 나서는 그 층의 전체 블럭수를 이용하여 x블럭의 위치를 뽑아낸다.

여기서 x의 범위가 1<= x <= 10^6 이기때문에 이 값을 빠르게 찾는 것이 중요했고, 이를 이분탐색을 이용해서 찾았다.