문제

나의 요약

0행 0열에 1, 0행 1열에 2를 쓰는 소용돌이가 거기서부터 반시계 방향으로 시작된다.
출력해야하는 좌표는 (r1, c1)가 가장 왼쪽 위, (r2, c2)가 가장 오른쪽아래이다.

이때 다음의 조건대로 출력하자.
1. r1부터 r2행까지 차례대로 출력한다.
2. 원소는 공백으로 구분한다.
3. 모든 행은 같은 길이이다.
4. 만약 수의 길이가 가장 길이가 긴 수보다 작다면, 공백을 삽입해 길이를 맞춘다..

접근 방법

총 소용돌이에서 나올 수 있는 수는 5000*5000*4-3이기 때문에 대략 1억에 가깝다. 따라서 소용돌이를 모두 직접 만들어보는 것은 무리가 있다. 특정한 규칙을 찾아야 하는데, 나는 0에서 대각선 값들을 기준으로 구하는 것을 목표로 했다.

다음 선에 있는 값들을 나누어 구한다.
r과 c가 모두 음수인 대각선 값은 minusminus에, r은 음수, c가 양수인 대각선 값은 minusplus에, r은 양수, c가 음수인 대각선 값은 plusminus에 저장한다.
저장해둔 대각선 값을 토대로 (r, c) 좌표의 값을 특정한 규칙에 따라 구할 수 있다.

아래 조건을 따르면 된다.

1. c가 음수고, 절댓값 c가 절댓값 r보다 크거나 같을때,
   1-1. minusminus[절댓값 c]를 가져온다.
   1-2. 그 값에 r-c만큼 더해주면 된다.

2. r이 양수고, (r이 절댓값 c보다 크거나 같을때, 혹은 c가 r보다 1클때)
   2-1. plusminus[절댓값 c]를 가져온다.
   2-2. 그 값에 r+c만큼 더해주면 된다.

3. c가 양수고, c가 절댓값 r보다 크거나 같을때,
   3-1 minusplus[c]를 가져온다.
   3-2. 그 값에 r+c만큼 빼준다.

4. r이 음수고, 절댓값 r이 절댓값 c보다 크거나 같을때,
   4-1. minusplus[절댓값 r]를 가져온다.
   4-2. 그 값에 절댓값 r + 절댓값 c만큼 더해준다.

이제 (r1, c1)부터 (r2, c2)까지 전부 저장해둔 뒤, 최고 숫자의 자릿수를 구해 자릿수대로 공백을 추가해 출력하면 된다.

풀이

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> nums;
vector<int> minusminus(5001);
vector<int> plusminus(5001);
vector<int> minusplus(5001);

int r1, c1, r2, c2;

void Input()
{
    cin >> r1 >> c1 >> r2 >> c2;
}

int FindSwirlNum(int r, int c)
{
    int num = 1;
    if(c < 0 && abs(c) >= abs(r))
    {
        num = minusminus[c*-1] + r-c;
    }
    else if(r >= 0 && (r >= abs(c) || c == r+1))
    {
        num = plusminus[r] + c+r;
    }
    else if(c >= 0 && c >= abs(r))
    {
        num = minusplus[c] - (c+r);
    }
    else if(r < 0 && abs(r) >= abs(c))
    {
        num = minusplus[r*-1] + (-r-c);
    }

    return num;
}

int GetDigits(int num)
{
    int digits = 0;
    while(num > 0)
    {
        num /= 10;
        digits++;
    }

    return digits;
}

void Solve()
{
    minusminus[0] = 1;    plusminus[0] = 1;    minusplus[0] = 1;
    minusminus[1] = 5;    plusminus[1] = 7;    minusplus[1] = 3;
    for(int i = 2; i <= 5000; i++)
    {
        minusminus[i] = minusminus[i-1] + (minusminus[i-1] - minusminus[i-2] + 8);
        plusminus[i] = plusminus[i-1] + (plusminus[i-1] - plusminus[i-2] + 8);
        minusplus[i] = minusplus[i-1] + (minusplus[i-1] - minusplus[i-2] + 8);
    }
    
    nums.assign(r2-r1+1, vector<int>(c2-c1+1));
    int maxNum = 0;
    for(int r = r1; r <= r2; r++)
    {
        for(int c = c1; c <= c2; c++)
        {
            nums[r-r1][c-c1] = FindSwirlNum(r, c);
            maxNum = max(maxNum, nums[r-r1][c-c1]);
        }
    }

    int maxDigits = GetDigits(maxNum);
    for(int r = r1; r <= r2; r++)
    {
        for(int c = c1; c <= c2; c++)
        {
            int num = nums[r-r1][c-c1];
            int digit = GetDigits(num);

            string blank = " ";
            
            for(int i = 0; i < (maxDigits-digit); i++)
            {
                cout << blank;
            }

            cout << num << " ";
        }
        cout << "\n";
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Solve();
}

FindSwirlNum 함수가 위에서 언급했던 대각선 값과 조건을 통해 (r, c)에 대한 소용돌이 값을 구하는 함수이다. 그대로 (r1, c1)부터 (r2, c2)까지 소용돌이 값을 구해 저장하면 된다.

회고

처음에 전체 소용돌이에 대한 값을 구하려고 하다가, 5000*5000이 아니고 5000*5000*4라는 것을 뒤늦게 알아차렸다. 차라리 처음부터 특정 규칙을 구하려고 했다면 조금 더 나았을 것 같다는 생각이 들었다. 좀 귀찮아 보인다고 일단 넘기지 말고 한번 빠르게 해보자..