[BOJ / C++] 25294 - 달팽이와 쿼리

백준 문제 링크 : 25294 - 달팽이와 쿼리

문제

입력

첫째 줄에 쿼리의 개수 $Q$가 주어진다. 둘째 줄부터 $Q$개의 줄에 쿼리가 한 줄에 하나씩 주어진다.

출력

쿼리를 수행한 결과를 한 줄에 하나씩 순서대로 출력한다.

제한

• $1 ≤ Q ≤ 100\,000$ 

• $3 ≤ n ≤ 9999$ 

• $1 ≤ x, y ≤ n$ 

• $1 ≤ z ≤ n^2$ 

입출력 예시

풀이

무턱대고 달팽이배열을 완성시키며 찾으려면 시간이 많이 걸릴 것 같습니다.
따라서 어떤 규칙을 찾아야 하는데,
문제에서 $n=3, 5$인 경우를 줬는데, $n=7$인 경우 또한 보면서 하면 규칙을 찾기 좀 쉬울 것 같습니다.
$n=7$인 경우의 달팽이 배열은 다음과 같습니다.

01 02 03 04 05 06 07
24 25 26 27 28 29 08
23 40 41 42 43 30 09
22 39 48 49 44 31 10
21 38 47 46 45 32 11
20 37 36 35 34 33 12
19 18 17 16 15 14 13

가독성을 위해 1을 01로 표현했습니다

가장 큰 수인 49까지 가는 과정을 생각해보면..

• $7 + 6 + 6 + 5 + 5 + 4 + 4 + 3 + 3 + 2 + 2 + 1 + 1 = 49$

따라서 제가 생각한 달팽이 배열의 규칙은 다음과 같습니다
$n * n$의 달팽이 배열에서 임의의 수 $z$에 도달하기 위해 변수 $cur$를 생각한다고 했을 때

1. 먼저, $cur$를 $n$에서부터 시작합니다. 찾고자 하는 수$z$가 $n$보다 작은 경우는 예외처리
2. 아래로 $n-1$만큼 가면 꺾어야 하며, 왼쪽으로 n-1만큼 가면 꺾어야 함
3. 이제 위로 $n-2$만큼 가면 꺾어야 하며, 오른쪽으로 n-2만큼 가면 꺾어야 함
4. 찾고자 하는 수 $z$까지 도달할 때 까지 2, 3번 과정을 $(n-i)$로 두어 반복합니다 ($i$를 2번마다 증가시키며).

2번째 쿼리에 해당하는 예시로 보시면 될 것 같습니다. 1번째 쿼리는 이를 $x,y$좌표로 가는 경우로만 생각하면 나머지는 비슷합니다.

코드를 보시면서 규칙을 다시 생각해보시면 좋을 것 같습니다

코드

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int query1(int n, int x, int y) {
	//n X n 달팽이배열에서 x, y좌표에 있는 수를 찾는다
	if (y == 1) return x;
	if (x == n/2+1 && y == n/2+1) return n*n;
	int cur = n;
	int curX = n, curY = 1;
	int flag = 0;
	int i = 1;
	while (1) {
		if (curX == x) {
			cur += y - curY;
			return cur;
		}
		curY += n-i;
		cur += n-i;
		if (curY == y) {
			cur += curX - x;
			return cur;
		}
		curX -= n-i;
		cur += n-i;
		i++;
		if (curX == x) {
			cur += curY - y;
			return cur;
		}
		curY -= n-i;
		cur += n-i;
		if (curY == y) {
			cur += x - curX;
			return cur;
		}
		curX += n-i;
		cur += n-i;
		i++;
	}
}

void query2(int n, int z) {
	if (z <= n) {
		cout << "1 " << z << "\n";
		return;
	}
	if (z == n*n) {
		cout << n/2+1 << " " << n/2+1 << "\n";
		return;
	}
	int cur = n;
	int curX = n, curY = 1;
	int flag = 0;
	int i = 1;
	while (1) {
		if (cur + n-i >= z) {
			curY += z - cur;
			cout << curY << " " << curX << "\n";
			return;
		}
		curY += n-i;
		cur += n-i;
		if (cur + n-i >= z) {
			curX -= z - cur;
			cout << curY << " " << curX << "\n";
			return;
		}
		curX -= n-i;
		cur += n-i;
		i++;
		if (cur + n-i >= z) {
			curY -= z - cur;
			cout << curY << " " << curX << "\n";
			return;
		}
		curY -= n-i;
		cur += n-i;
		if (cur + n-i >= z) {
			curX += z - cur;
			cout << curY << " " << curX << "\n";
			return;
		}
		curX += n-i;
		cur += n-i;
		i++;
	}
}

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

	int q;
	cin >> q;
	for(int i=0;i<q;i++) {
		int t;
		cin >> t;
		if (t == 1) {
			//n, x, y 쿼리
			int n, x, y;
			cin >> n >> x >> y;
			cout << query1(n,y,x) << "\n";
		}
		else if (t == 2) {
			//n, z 쿼리
			int n, z;
			cin >> n >> z;
			query2(n,z);
		}
	}
}

원래 각 쿼리에서, 4방향 이동 각각 while문 사이클을 돌도록 했는데, 72%에서 시간초과가 떠서 4방향 이동을 모두 while문의 한 사이클로 작성하니 시간초과를 피할 수 있었습니다.