취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 27261번 문제인 Номера по диагонали이다.
문제는 아래 링크를 확인하자.

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

R행 C열의 칸을 문제에서 주어진 규칙과 같이 채워나갈 때 각 주어지는 수가 쓰여진 칸의 행과 열을 각각 출력하는 문제이다.

R이 C보다 작다고 가정해보자. 이 때, 좌상단의 R(R-1)/2까지의 수와 우하단의 RC-R(R-1)/2를 초과하는 수들을 제외한 남은 수들은 매우 규칙적인 배열을 하고 있음을 관찰할 수 있다. 또한, 좌상단 또는 우하단에 있는 수들의 위치는 각 수가 몇 번째 대각선에 있는지를 이진탐색 등을 이용해 알아내는 것으로 빠르게 구해낼 수 있음을 관찰할 수 있다.

마찬가지로 R이 C보다 큰 경우에도 칸에 적힌 수들의 규칙을 유사하게 분석할 수 있음을 관찰할 수 있다. 이와 같은 관찰과 같이 경우를 나누어 문제의 답을 찾는 코드를 작성하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll R, C, Q;

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

	cin >> R >> C >> Q;
	
	if (R < C) {
		while (Q--) {
			ll X; cin >> X;
			if (X <= R * (R - 1) / 2) {
				ll dL = 1, dR = R - 1;
				while (dL < dR) {
					ll mid = (dL + dR) / 2;
					if (X <= mid * (mid + 1) / 2) dR = mid;
					else dL = mid + 1;
				}
				cout << X - dL * (dL - 1) / 2 << ' ' << (dL + 1) - (X - dL * (dL - 1) / 2) << '\n';
			}
			else if (X > R * C - R * (R - 1) / 2) {
				X = R * C - X + 1;
				ll dL = 1, dR = R - 1;
				while (dL < dR) {
					ll mid = (dL + dR) / 2;
					if (X <= mid * (mid + 1) / 2) dR = mid;
					else dL = mid + 1;
				}
				cout << (R + 1) - (X - dL * (dL - 1) / 2) << ' ' << (C + 1) - ((dL + 1) - (X - dL * (dL - 1) / 2)) << '\n';
			}
			else {
				ll D = (X - R * (R - 1) / 2 - 1) / R;
				cout << (X - R * (R - 1) / 2 - 1) % R + 1 << ' ' << R - ((X - R * (R - 1) / 2 - 1) % R) + D << '\n';
			}
		}
	}
	else {
		while (Q--) {
			ll X; cin >> X;
			if (X <= C * (C - 1) / 2) {
				ll dL = 1, dR = C - 1;
				while (dL < dR) {
					ll mid = (dL + dR) / 2;
					if (X <= mid * (mid + 1) / 2) dR = mid;
					else dL = mid + 1;
				}
				cout << X - dL * (dL - 1) / 2 << ' ' << (dL + 1) - (X - dL * (dL - 1) / 2) << '\n';
			}
			else if (X > R * C - C * (C - 1) / 2) {
				X = R * C - X + 1;
				ll dL = 1, dR = C - 1;
				while (dL < dR) {
					ll mid = (dL + dR) / 2;
					if (X <= mid * (mid + 1) / 2) dR = mid;
					else dL = mid + 1;
				}
				cout << (R + 1) - (X - dL * (dL - 1) / 2) << ' ' << (C + 1) - ((dL + 1) - (X - dL * (dL - 1) / 2)) << '\n';
			}
			else {
				ll D = (X - C * (C - 1) / 2 - 1) / C;
				cout << (X - C * (C - 1) / 2 - 1) % C + D + 1 << ' ' << C - (X - C * (C - 1) / 2 - 1) % C << '\n';
			}
		}
	}
}