[BOJ] 28127. 숫자탑과 쿼리

BOJ 28127. 숫자탑과 쿼리
2023 아주대학교 프로그래밍 경시대회 APC Div.1 C번
Math 

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

28127번: 숫자탑과 쿼리

1. 문제 설명

숫자가 적힌 블록으로 탑 쌓기를 하는데, 아래의 규칙대로 탑을 쌓는다.

1. top이 1층이고, bottom으로 내려갈수록 깊은 층이다.
2. 1층에는 a개의 블록이 존재한다.
3. i번째 층의 가장 오른쪽 블록은 i+1번째 층의 가장 왼쪽 블록보다 1만큼 크다.
4. i번째 층에 있는 블록의 수보다 i+1번째 층에 있는 블록의 수가 d개 더 많다.

3번이 다소 이해되지 않을 수 있는데, 그림과 함께 보면 쉽다. (a=1, d=2인 경우)

출처 - 백준 28127번

2층에서 2, 3, 4번 블록까지 모두 놓아서 다음 층으로 가야하면, 다음 층의 첫 블록은 5번이라는 소리다.

당연한 소리..

 

아 그리고 굳이 블록을 피라미드 형태로 놓을 필요 없고, 그냥 왼쪽으로 다 붙여도 문제없다.

만약 a=2, d=3 이라면 아래와 같이 숫자가 배열될 것이다.

1  2
3  4  5  6  7
8  9 10 11 12 13 14 15
...

이러한 숫자의 나열에서 규칙을 찾으면 된다.

---

2. 문제 접근

우선 n을 찾아야 하는데, 잘 보면 각 층별로 계차수열임을 알 수 있다.

n을 찾으면 출력의 (s, t) 에서 s를 찾을 수 있다. (n과 s가 같을 것이다.)

 

이때, n을 찾기 위해 naive하게 1부터 값을 1씩 증가시켜서 찾아도 되고,

조금 머리를 쓴다면 binary search로 해결할 수도 있다.

 

TMI로 대회 당시에.. 대충 계산해보니 naive하게 찾아도 될 것 같아서 하나씩 올렸습니다.

다만, 파이썬의 경우 시간이 빡빡하므로 pypy로 제출해야 통과된다는..

 

이후 해당 층에서 몇 번째 블록인지 찾는 것은 x와 이전 블록까지의 합의 차를 구하면 끝!

 

말로 설명해서 복잡해보이지만, (계차수열을 안다는 가정 하에)코드로 보면 매우 단순하다.

 

---

3. 구현 코드

from sys import stdin

q = int(stdin.readline())
for _ in range(q):
    a, d, x = map(int, stdin.readline().split())
    n = 1
    while a*n + ((n*(n-1)*d) >> 1) < x:
    	n += 1
    print(n, x - (a*(n-1) + (((n-1)*(n-2)*d) >> 1)))

while loop가 n을 찾는 과정이다. (몇 층인지 찾는 것과 동일)

이때, 조금이라도 시간을 아끼려고 bit shift 연산을 사용했다.

python3로 돌리니까 간당간당하게 시간초과떠서.. 너무 슬펐다.