백준] 10157 - 자리배정(한국정보올림피아드;KOI 2014 지역본선)

시간 제한 : 1초

메모리 제한 : 256MB

입력

첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. 단 1 ≤ K ≤ 100,000,000이다.

출력

입력으로 제시된 대기번호 K인 관객에게 배정될 좌석번호 (x,y)를 구해서 두 값, x와 y를 하나의 공백을 사이에 두고 출력해야 한다. 만일 모든 좌석이 배정되어 해당 대기번호의 관객에게 좌석을 배정할 수 없는 경우에는 0(숫자 영)을 출력해야 한다. 

소스코드

#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
	int dir[4][2] = { {0,-1},{1,0},{0,1},{-1,0} }, d = 0;
	int c, r, k, cnt = 1, x, y;
	cin >> c >> r >> k;
	
	if (k > c*r)
		cout << 0;
	else
	{
		vector<vector<int> > seat(r, vector<int>(c, 0));
		y = r - 1, x = 0;
		while (cnt < k)
		{
			int dx = x + dir[d][0];
			int dy = y + dir[d][1];

			if (dx < 0 || dx >= c || dy < 0 || dy >= r || seat[dy][dx]!=0)
			{
				d = (d + 1) % 4;
				continue;
			}

			seat[y][x] = cnt++;
			y = dy, x = dx;
		}
		cout << x + 1 << ' ' << r - y;
	}
}

Tip

이 문제는 흔히 말하는 숫자 달팽이를 만들어가면서 자신이 원하는 대기번호가 나올 때 좌석번호를 출력하는 식으로 해결할 수 있다. 숫자 달팽이를 만들어되지 않아도 되는 경우는, 대기 번호가 좌석수보다 큰 경우에는 모든 관객이 이미 배정된 경우이기 때문에 바로 0을 출력하면 된다.