백준 1022번 소용돌이 예쁘게 출력하기[C++]

1. 문제 풀이

1-1. 문제 개요

 안녕하세요. 오늘 풀어볼 문제는 백준 1022번 소용돌이 예쁘게 출력하기입니다. 문제의 유형은 수학입니다. 이 문제는 주어진 소용돌이에서 규칙을 찾아 구현하여 풀이하는 문제입니다. 수학적 규칙을 찾는 것에 어려움을 느끼는 저에게는 수학뿐 아니라 그리디, 동적 계획 유형의 문제들이 항상 버겁습니다. 하지만 극복해야 할 관문인 것 같습니다. 문제를 풀기 위해서 고려해야 할 구현은 두 가지입니다. 임의의 좌표가 주어졌을 때, 소용돌이에서 좌표가 가르키는 숫자를 찾는 방법, 출력해야할 숫자의 최댓값의 자릿수보다 부족할 때, 부족한 자릿수만큼 공백을 삽입해서 출력하는 방법 이 두 개입니다.

 

1-2. 좌표로 소용돌이 숫자 찾기

 문제에서 각 좌표의 숫자가 위와 같은 그림과 같은 규칙으로 이루어져 있다고 설명합니다. 이 내용만 읽으면 단순히 배열을 하나 선언해서 규칙대로 숫자를 갱신하면 되겠다는 생각이 들었습니다. 하지만 좌표의 범위가 최대 -5,000에서 5,000까지 주어진다는 조건이 있습니다. 이 조건을 만족하면서 배열로 문제를 풀이하려면 배열의 크기가 최대 100,000,000이어야 합니다. 문제의 메모리 제한이 125MB이므로 배열로 선언해서 풀이하는 것은 불가능합니다.

 

 따라서, 소용돌이에서 규칙을 찾아 구현하여 풀이해 보도록 하겠습니다.

쉽게 찾을 수 있는 규칙은 그림과 같습니다.

 

임의의 좌표 ( x, y )에 대해서 x, y는 음이 아닌 정수이고, x = y이면 해당 좌표의 값은 ( 2x + 1 )² 입니다.

 

이렇게 찾은 규칙을 가지고 임의의 좌표의 값을 찾을 수 있는지 확인해 보도록 합시다.

 

예를 들어, 좌표 ( -2, 0 )의 값을 찾아보도록 합시다.

 

 

좌표 ( -2, 0 )을 가지고 유추할 수 있는 정보가 무엇일지 고민해 봅시다. 위에서 찾은 규칙과 가까운 두 수는 아래와 같습니다.

 

9는 ( 1, 1 )의 값이고 ( -2, 0 )이라는 좌표만 가지고 찾을 수 있을지는 잘 모르겠습니다. 25는 ( 2, 2 )의 값이고 ( -2, 0 )에서 -2인 x값과 관련이 있어 보이지만 확실하진 않습니다. 처음에 찾은 규칙의 숫자들을 기준으로 정사각형을 그려보면 또 다른 규칙이 있음을 찾을 수 있습니다.

저 초록색 사각형 내부의 숫자들의 좌표에서 또 하나의 규칙을 찾을 수 있습니다.

초록색 내부의 숫자들 중 임의의 좌표 ( x, y )에 대해서 x 또는 y 값 중 적어도 하나는 절댓값이 2입니다.

따라서, 이를 통해 x, y의 절대값이 가장 큰 값을 찾아 처음 찾은 규칙을 적용해 25라는 값을 구할 수 있습니다.

 

임의의 좌표 ( x, y )에 대해서 |x| > |y|이면 ( x, y )의 값은 ( 2*|x| + 1 )² 보다 작거나 같다.

또한, |x| < |y|이면 ( x, y )의 값은 ( 2*|y|+1 )²보다 작거나 같다.

 

그리고 다음과 같은 조건을 순서대로 수행하면 되겠습니다.

찾으려는 좌표가 ( x, y ) = ( -2, 0 )이라고 해봅시다.

 

( x == 2 )인 경우 : 25에서 y 값을 가지고 적절히 뺄셈을 수행해 좌표의 값을 찾을 수 있습니다.

 

만약, x가 2가 아니라면 이동합니다.

 

 

25가 ( 2, 2 ) 좌표의 값이므로 25 - ( 2 * 2 )연산으로 사각형의 각 가장자리로 이동이 가능합니다.

 

(y == -2 )인 경우 : x 값을 사용해 적절히 뺄셈을 하면 값을 찾을 수 있습니다.

 

만약, y가 -2가 아닌 경우 다른 가장자리로 이동합니다.

 

( x == -2인 경우 ) : 우리가 구하고자 하는 좌표는 ( -2, 0 )이므로 제대로 찾아왔습니다. y의 값은 0입니다. 그렇다면 17 - 2 - y 뺄셈을 수행하면 좌표 내 값을 찾을 수 있습니다.

 

만약에 x가 -2가 아니라면 같은 규칙으로 한 번 더 이동해서 구하시면 되겠습니다.

 

어떤 방법으로 뺄셈 해야 하는지는 쉽게 찾을 수 있습니다. 만약 어렵다고 생각하신다면, 아래의 코드를 확인해 주세요.

 

1-3. 공백 삽입 방법

이렇게 구한 숫자들을 배열을 선언해 저장했습니다. 배열에서 가장 큰 값을 찾은 후 문자열로 형변환해 길이를 구해주었습니다. 그다음, 숫자를 출력하기 전에 부족한 길이만큼 공백을 출력해 해결했습니다.

 

1-4. 시간복잡도 분석

임의의 좌표에서 값을 찾는 로직은 O(1)입니다. 그리고 찾아야 할 좌표의 총개수는 (r2-r1)*(c2-c1)입니다.

 

따라서 시간복잡도는 O((r2-r1)*(c2-c1))으로 시간 내 통과가 가능합니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define X first
#define Y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';
int sx, sy, ex, ey;
int ans[55][5];
int get_num(int row, int col){
  int n = max(abs(row), abs(col));
  int ret = (2*n+1)*(2*n+1);
  if(row == n) return ret - n + col;
  ret -= 2*n;
  if(col == -n) return ret - n + row;
  ret -= 2*n;
  if(row == -n) return ret - n - col;
  ret -= 2*n;
  return ret - n - row;
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> sx >> sy >> ex >> ey;
  int i{}, j{};
  for(int row = sx; row <= ex; row++){
    for(int col = sy; col <= ey; col++){
      ans[i][j++] = get_num(row, col);
    }
    i++; j = 0;
  }
  int rmx = ex - sx + 1;
  int cmx = ey - sy + 1;
  int sz = to_string(*max_element(&ans[0][0], &ans[rmx][cmx])).size();
  for(int i = 0; i < rmx; i++){
    for(int j = 0; j < cmx; j++){
      for(int k = to_string(ans[i][j]).size(); k < sz; k++) cout << ' ';
      cout << ans[i][j] << ' ';
    }
    cout << nl;
  }

}

 

3. 제출 결과