[C++ / Algorithm] 백준 28127번 숫자탑과 쿼리 #22

1. 트리

1-1. 문제

의찬이는 숫자가 적힌 블록으로 탑 쌓기를 즐긴다. 어느 날 선우는 의찬이가 쌓는 탑에 규칙이 있음을 알게 되었다! 선우가 알아낸 규칙은 다음과 같다.

• 의찬이가 쌓는 탑은 꼭대기가 1층이고, 1층에는 a개의 블록이 존재한다.
• 1층의 가장 왼쪽 블록에는 1이 적혀있으며, 블록에 적힌 숫자는 오른쪽으로 갈수록 1씩 증가한다.
• i번째 층의 가장 오른쪽 블록보다 i+1번째 층의 가장 왼쪽 블록이 1더 크다.
• i번째 층에 있는 블록의 수보다 i+1번째 층에 있는 블록의 수가 d개 더 많다.

아래 그림은 1에서 4층까지 a=1이고 d=2일 때 의찬이가 쌓은 탑의 모습이다.

각 숫자가 적힌 블록의 위치를 모조리 외운 의찬이는 선우가 던지는 Q개의 질문에 답하고자 한다. 질문은 한 가지 형식이다.

• a d x: a와 d가 주어질 때, x가 적힌 숫자 블록이 몇 번째 층의 몇 번째 숫자인가?

위 그림을 예로 들자. 만약 a=1, d=2, x=12라면 의찬이는 (4,3)이라고 대답한다. 이는 12가 적힌 숫자 블록이 4층에 위치한 3번째 숫자라는 것을 의미한다.

1-2. 입력

첫째 줄에는 선우가 의찬이에게 하는 질문의 개수 Q가 주어진다. (1 <= Q <= 500,000) 

이후 Q개의 줄에는 a, d, x가 공백으로 구분되어 주어진다. (1 <= a,d,x <= 1000000) 

입력으로 주어지는 모든 값은 정수다.

2. 풀이

n번째 줄의 제일 오른쪽 수보다 n + 1번째 줄의 제일 왼쪽 수가 항상 크므로 1부터 1000000까지의 줄을 이분 탐색한다면 빠르게 문제를 해결할 수 있다.

n번재 줄의 제일 왼쪽 수를 구하는 공식은 다음과 같다. An = (n - 1)(2a + (n - 2)d) / 2 + 1

#include <iostream>
#include <cmath>

using namespace std;

long long getLeft(long long a, long long d, long long n) {
	return (n - 1) * (2 * a + (n - 2) * d) / 2 + 1;
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int numberOfQueries;
	int a, d, value;

	cin >> numberOfQueries;

	while (numberOfQueries--) {
		cin >> a >> d >> value;

		long long start = 1;
		long long end = 1000000;
		long long x, y;

		while (start <= end) {
			long long middle = (start + end) / 2;
			long long left = getLeft(a, d, middle);

			if (left <= value) {
				start = middle + 1;
				x = left;
				y = middle;
			}
			else {
				end = middle - 1;
			}
		}
		cout << y << ' ' << value - x + 1 << '\n';
	}
}

2
1 2 12
1 2 17

4 3
5 1