백준 1022 소용돌이 예쁘게 출력하기

문제 : https://www.acmicpc.net/problem/1022

서론

처음엔 소용돌이 전체를 배열에 저장한 후 출력하려 했으나 소용돌이 배열만 400MB로 메모리 초과가 발생했다.

그래서 소용돌이전체 중 출력을 해야하는 부분만 배열에 저장하기로했다.

쉽게 봤으나 반례찾기 등 시행착오를 상당히 많이 거친 문제.

구현 전에 확실히 가능성검토를 해야 시간을 아낄 수 있다.

아이디어

소용돌이는 규칙성이 있다.

수	1	2	3	4	5	6	7	8	9
회전방향	오른쪽	위쪽	왼쪽	아래쪽	오른쪽	위쪽	왼쪽	아래쪽	오른쪽
이동칸	1	1	2	2	3	3	4	4	5

1을 시작으로 오른쪽으로 1칸 전진한 2

2를 시작으로 위쪽으로 1칸 전진한 3

3을 시작으로 왼쪽으로 2칸 전진한 5

5를 시작으로 아래로 2칸 전진한 7

7을 시작으로 오른쪽으로 3칸 전진한 10

10을 시작으로 위쪽으로 3칸 전진한 13

13을 시작으로 왼쪽으로 4칸 전진한 17

17을 시작으로 아래쪽으로 4칸 전진한 21

....

즉 회전을 두번 할때마다 이동하는 칸수가 하나씩 증가한다

그리고 회전은 오른쪽, 위쪽, 왼쪽, 아래를 반복한다

결과적으로 오른쪽과 왼쪽 회전시마다 이동하는 칸수가 하나씩 증가한다

이것을 구현하면 되는데 소용돌이 전체를 배열에 넣으면 메모리초과가 발생한다

따라서 r1,c1,r2,c2 범위 안에 있는 숫자들만 배열에 입력한다

예쁘게 출력하는 법은 출력하는 숫자들 중 가장 큰 숫자의 자리수와 현재 출력의 대상이 되는 숫자의 자리수를 비교해 차이만큼 띄어쓰기를 추가

구현

Q. numPrint

A. 출력되는 숫자의 개수로, numPrint만큼만 배열에 저장함

Q. maxInput

A. 출력되는 숫자 중 가장 큰 수로 자리수 비교대상

Q. 라인33 if (x >= c1 && x <= c2 && y >= r1 && y <= r2) {

A. 소용돌이의 첫 1은 위 아이디어의 규칙성이 적용되지 않음. 1이 출력대상이라면 출력배열에 삽입

//C++

#pragma warning(disable : 4996)

#include <cstdio>
#include <iostream>

using namespace std;

int map[50][5];
int r1, c1, r2, c2;
int numPrint;
int maxInput;

void input() {
	cin >> r1 >> c1 >> r2 >> c2;
	numPrint = (abs(r2 - r1)+1)*(abs(c2 - c1)+1);
	//cout << "numPrint : " << numPrint << endl;
}

void createMap() {
	// right, up, left, down
	int dx[4] = { 1, 0, -1, 0 };
	int dy[4] = { 0, -1, 0, 1 };
	int dir = -1;
	int len = 0;
	int input = 1;
	int x = 0;
	int y = 0;
	int cnt = 1;

	// 1을 map에 삽입
	if (x >= c1 && x <= c2 && y >= r1 && y <= r2) {
		map[y - r1][x - c1] = input;
		cnt++;
	}

	while (cnt <= numPrint) {
		dir = (dir + 1) % 4;
		if (dir == 0 || dir == 2) len++;
		for (int i = 0; i < len; i++) {
			input++;
			x += dx[dir];
			y += dy[dir];
			if (x >= c1 && x <= c2 && y >= r1 && y <= r2 ) { 
				map[y-r1][x-c1] = input; 
				//cout <<" y " << y << " x " << x << " input " << input << endl;
				cnt++;
				//cout << cnt << endl;
				maxInput = input;
			}
		}
	}
}

int digit(int input) {
	int result = 0;
	while (1) {
		result++;
		input /= 10;
		if (input == 0) break;
	}
	return result;
}

void print() {
	int refLen = digit(maxInput);
	for (int i = 0; i <= abs(r2 - r1); i++) {
		for (int j = 0; j <= abs(c2 - c1); j++) {
			for (int k = 0; k < refLen - digit(map[i][j]); k++) {
				printf(" ");
			}
			printf("%d ", map[i][j]);
		}
		printf("\n");
	}
}

int main() {
	input();
	createMap();
	print();
}