[ boj : 1022] 소용돌이 예쁘게 출력하기

www.acmicpc.net/problem/1022

1022번: 소용돌이 예쁘게 출력하기

문제 : 회전하는 배열을 주어진 범위에 맞게 예쁘게 출력해라

 

해설 : 다른 분들보면 어떻게 공식을 도출해서 풀었던데 난 모르겠음;;;; 그래서 그냥 노가다로 품.

노가다로 푸는 방법도 효율적이게 문제에 접근해야 된다.

단순히 10000x10000 배열을 잡고 수들을 채우고 범위에 맞는 수들을 출력하게끔 하면 되겠지!!!라고 생각하면 안된다.

이유는 제한 메모리는 128MB 바이트인데 10000x10000 배열을 잡으면 범위를 넘어서기 때문....

 

그러면 어떻게 해야되는 건가?

• 0<=r2-r1<=49
• 0<=c2-c1<=5

이 조건을 이용하면 된다.

 

방법은 이렇다. (0,0) 부터 배열을 돌린다. 그러면 조건에 맞는 범위에 해당하는 수가 나올 것이다. 그럼 이 수를 답으로 도출할 배열에 대입해준다. 그리고 출력하면 된다.

 

#include<bits/stdc++.h>

using namespace std;

int Max = -1;
int board[50][5];
vector<int> v;

int cal(int x);
void solve();
void go(int r1, int c1, int r2, int c2);

int main()
{
	solve();
}
void solve()
{
	int r1, c1, r2, c2;
	cin >> r1 >> c1 >> r2 >> c2;

	go(r1, c1, r2, c2);

	int len = cal(Max);
	for (int i = 0; i < abs(r1 - r2) + 1; i++) {
		for (int j = 0; j < abs(c1 - c2) + 1; j++)
		{
			int ret = cal(board[i][j]);
			for (int k = 0; k < len - ret; k++)
				cout << " ";
			cout << board[i][j] << " ";
		}
		cout << "\n";
	}
}
int cal(int x) 
{
	int ret = 0;
	while (x > 0) {
		ret++;
		x /= 10;
	}
	return ret;
}
void go(int r1, int c1, int r2, int c2)
{
	int dx[] = { 0,-1,0,1 }, dy[] = { 1,0,-1,0 };
	int x = 0, y = 0,d=0;
	int len = 1, tlen = 0, cnt = 0, num = 1;

	if (r1 <= x && x <= r2 && c1 <= y && y <= c2) {
		board[abs(x - r1)][abs(y - c1)] = num;
		cnt++;
		Max = max(Max, num);
	}

	while (true) {
		for (int i = 0; i < len; i++) {
			x = dx[d] + x;
			y = dy[d] + y;
			num++;
			if (r1 <= x && x <= r2 && c1 <= y && y <= c2) {
				board[abs(x - r1)][abs(y - c1)] = num;
				cnt++;
				Max = max(Max, num);
			}
		}
		d = (d + 1) % 4;
		if (cnt >= (abs(r1 - r2) + 1) * (abs(c1 - c2) + 1))break;
		tlen++;
		if (tlen % 2 == 0) {
			len++;
			tlen = 0;
		}
	}
}