[BOJ/Gold 5] 백준 25294 달팽이와 쿼리(C++)

문제 링크

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

25294번: 달팽이와 쿼리

 

문제

크기가 N인 이차원 달팽이 배열은 다음과 같이 정의된다.

•  N은 1보다 큰 홀수이다.
• 이차원 배열의 크기는 N×N이다.
•  1보다 크거나 같고, N^2보다 작거나 같은 자연수가 중복없이 1, 2, …, N^2 순서로 시계방향 소용돌이 패턴으로 한 칸에 하나씩 들어있다.
• 가장 왼쪽 윗 칸은 1이다.

왼쪽 그림은 크기 N이 3, 오른쪽은 5인 경우 이차원 달팽이 배열이다.

쿼리는 총 두 종류가 있다.

• 1 n x y: 크기가 n인 이차원 달팽이 배열에서 x행 y열에 들어있는 수를 출력한다.
• 2 n z: 크기가 n인 이차원 달팽이 배열에서 z가 들어있는 행 번호와 열 번호를 공백으로 구분해 출력한다.

행과 열의 번호는 1부터 시작한다.

 Q개의 쿼리가 주어진다. 쿼리를 순서대로 수행해보자.

입력

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

출력

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

제한

•  1≤Q≤100000
•  3≤n≤9999
•  1≤x,y≤n
•  1≤z≤n^2

예제 입력 1

10
1 3 1 1
1 3 2 1
1 3 2 2
2 3 9
2 3 6
1 5 2 2
1 5 4 2
2 5 4
2 5 22
1 5 3 2

예제 출력 1

1
8
9
2 2
3 2
17
23
1 4
4 3
24

알고리즘 분류

• 수학
• 구현

풀이

N이 작았다면 3부터 N까지 N*N의 크기를 갖는 소용돌이 패턴을 갖는 배열 N/2개를 다 미리 구현해 놓고 답을 찾을 수 있었겠지만 N이 9999까지이기 때문에 그러기에는 무리가 있다고 생각하였다.

그래서 우선 각 N마다 몇 번째 외곽에 무슨 숫자가 있는 지 파악하였다.

Q가 1로 시작한다면 (X, Y)가 몇 번째 외곽에 있는 지 계산한 후 외곽의 시작점부터 시계 방향으로 돌면서 (X, Y)와 일치하는 좌표에 있는 숫자를 출력하였다.

Q가 2로 시작한다면 Z가 몇 번째 외곽에 있는 지 파악한 후 외곽의 시작점부터 시계 방향으로 돌면서 Z와 일치하는 숫자가 있는 좌표를 출력하였다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0);
#define MAX 5000

using namespace std;
int Q, N, X, Y, Z;
vector<int> Vec[MAX];

void init() {
    Vec[0].push_back(0);
    Vec[0].push_back(1);
    int Number = 0;
    for (int i = 1; i < MAX; i++) {
        Number += 8;
        Vec[i].push_back(0);
        Vec[i].push_back(Number);
        for (int j = 1; j < Vec[i - 1].size(); j++) {
            Vec[i].push_back(Vec[i - 1][j] + Number);
        }
    }
}

void first_Query() {
    if (((N / 2) + 1 == X) && ((N / 2) + 1 == Y)) {
        cout << N * N << "\n";
    }
    int Center = (N / 2) + 1;
    int SubX = abs(Center - X);
    int SubY = abs(Center - Y);
    int Big = max(SubX, SubY);
    int Number = Center - Big;
    int Start = Vec[N / 2][Number - 1] + 1;
    int Len = N - ((Number - 1) * 2);
    int CurX = Number;
    int CurY = Number;
    Len--;
    for (int i = 0; i < Len; i++) {
        if ((CurX == X) && (CurY == Y)) {
            cout << Start << "\n";
            return;
        }
        CurY++;
        Start++;
    }
    for (int i = 0; i < Len; i++) {
        if ((CurX == X) && (CurY == Y)) {
            cout << Start << "\n";
            return;
        }
        CurX++;
        Start++;
    }
    for (int i = 0; i < Len; i++) {
        if ((CurX == X) && (CurY == Y)) {
            cout << Start << "\n";
            return;
        }
        CurY--;
        Start++;
    }
    for (int i = 0; i < Len; i++) {
        if ((CurX == X) && (CurY == Y)) {
            cout << Start << "\n";
            return;
        }
        CurX--;
        Start++;
    }
}

void second_Query() {
    if (N * N == Z) {
        cout << (N / 2) + 1 << " " << (N / 2) + 1 << "\n";
        return;
    }
    int Number = 0;
    int Start = 0;
    for (int i = 1; i < Vec[N / 2].size(); i++) {
        int Cur = Vec[N / 2][i - 1];
        int Next = Vec[N / 2][i];
        if ((Z > Cur) && (Z <= Next)) {
            Number = i;
            Start = Cur + 1;
            break;
        }
    }
    int Len = N - ((Number - 1) * 2);
    for (int i = 0; i < Len; i++) {
        if (Z == Start) {
            cout << Number << " " << Number + i << "\n";
            return;
        }
        Start++;
    }
    Len--;
    for (int i = 0; i < Len; i++) {
        if (Z == Start) {
            cout << Number + 1 + i << " " << N - Number + 1 << "\n";
            return;
        }
        Start++;
    }
    for (int i = 0; i < Len; i++) {
        if (Z == Start) {
            cout << N - Number + 1 << " " << N - Number - i << "\n";
            return;
        }
        Start++;
    }
    Len--;
    for (int i = 0; i < Len; i++) {
        if (Z == Start) {
            cout << N - Number - i << " " << Number << "\n";
            return;
        }
        Start++;
    }
}

void input() {
    cin >> Q;
    while (Q--) {
        int I;
        cin >> I;
        if (I == 1) {
            cin >> N >> X >> Y;
            first_Query();
        }
        else if (I == 2) {
            cin >> N >> Z;
            second_Query();
        }
    };
}

int main() {
    FASTIO
    init();
    input();

    return 0;
}