※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
소용돌이 형태로 숫자가 전개되고 있는 판에서, 특정 부분을 떼었을 때 그 부분을 출력하는 문제입니다.
이러한 문제를 접근할 때 우리가 생각할 수 있는 포인트는, 정말로 직접 소용돌이를 그려보면서 가는 것입니다. 즉, 시뮬레이션을 합니다.
하지만 주어진 범위를 모두 시뮬레이션 하면 시간 초과가 발생하므로, 애초에 잘라진 영역이 아닌 부분을 그리는 경우는 그리지 않고 스킵해주는 방식으로 넘어가면 시간을 상당히 줄일 수 있습니다. 그러기 위해서는 소용돌이의 규칙을 파악해 봅니다.
소용돌이는 →, ↑, ←, ↓ 의 순서로 순서로 회전하며, 맨 처음을 제외하고 좌, 우로 움직일 경우에 이동하는 횟수가 1회씩 증가합니다. 이것을 짧게 글로 표현하면 우1,상1,좌2,하2,우3,상3,좌4,하4 형식으로 됩니다. 규칙성을 찾을 수 있겠죠? 맨 가운데를 0,0으로 잡고 해당 규칙을 적용시켜 좌표를 이동할 때, 어떠한 경우에도 우리가 구하고 싶은 영역에 들어가지 않는 부분이면 통째로 점프합니다. 이외의 경우 정말로 소용돌이를 그려가며 출력합니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int xdir[] = { 0,-1,0,1 }, ydir[] = { 1,0,-1,0 }, ptr, sz=1, buf;
string ans[55][55];
int main()
{
int r1, c1, r2, c2, x = 0, y = 0, cx, cy, sn = 1, mxl = 0;
cin >> r1 >> c1 >> r2 >> c2;
cx = -r1, cy = -c1;
for (int i = 0; i <= 30000; i++)
{
if ((r1 <= x && x <= r2) || (c1 <= y && y <= c2))
{
int tx = x, ty = y;
for (int j = 0, k = sn; j <= sz; j++, k++)
{
if (r1 <= tx && tx <= r2 && c1 <= ty && ty <= c2)
{
ans[tx + cx][ty + cy] = to_string(k);
mxl = max(mxl, (int)to_string(k).length());
}
tx += xdir[ptr], ty += ydir[ptr];
}
}
x += sz*xdir[ptr];
y += sz*ydir[ptr];
sn += sz;
buf++;
if (buf == 2) sz++, buf = 0;
ptr = (ptr + 1) % 4;
}
for (int i = r1 + cx; i <= r2 + cx; i++)
{
for (int j = c1 + cy; j <= c2 + cy; j++)
{
while (ans[i][j].length() < mxl) ans[i][j] = " " + ans[i][j];
cout << ans[i][j] << " ";
}
cout << "\n";
}
}