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

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

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

 

 

 

 

 

 

<접근방법>

구현 문제입니다.

메모리를 넉넉하게 사용할 수 있는 상황이라면 쉽게 구현할 수 있습니다.

한 껍데기에서 최저값 혹은 최대값을 기준으로 점진적으로 증가 혹은 감소를 하는 방법을 통해서 말이죠.

하지만 메모리가 부족한 상황입니다.

그래서 정확히 출력 범위에 대해서만 메모리를 사용해야 합니다.

 

그렇다면 결국엔 좌표를 통해서 값을 알아내야 합니다.

 

좌표 (y, x)

n : max(abs(y), abs(x))    (*abs() : 절대값)

한 껍데기에서 최대값 M :  (n * 2 + 1) ^ 2

 

좌표를 관찰해보시면 같은 껍데기에서는 n의 값이 항상 같습니다.

즉, 자기가 속한 껍데기의 최대값은 어느 좌표에서나 구할 수 있습니다.

 

자기가 포함된 영역을 구한 후에, 좌표를 통해서 영역 속의 최대값과의 차이를 구해서

값을 계산하면 됩니다.

 

영역

 

<느낀 점>

재귀로 자리수 구하는 방법

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
using namespace std;

int r1, c1, r2, c2, max_num;
int dy[4] = {0, -1, 0, 1};
int dx[4] = {-1, 0, 1, 0};
int  map[50][5], num[50][5];

int val_cal(int i, int j) {
	int n = max(abs(i), abs(j));
	int val = 2 * n + 1;
	val *= val;

	int diff = 2 * n;
	if (i == n) {
		return val - (n - j);
	}
	val -= diff;
	if (j == -n) {
		return val - (n - i);
	}
	val -= diff;
	if (i == -n) {
		return val - (n + j);
	}
	val -= diff;
	if (j == n) {
		return val - (n + i);
	}
}

int w(int val) {
	return val ? w(val / 10) + 1 : 0;
}

void simul() {
	int y_idx = 0, x_idx = 0;
	for (int i = r1; i <= r2; i++) {
		for (int j = c1; j <= c2; j++) {
			map[y_idx][x_idx] = val_cal(i, j);
			x_idx++;
		}
		y_idx++; x_idx = 0;
	}

	max_num = 0;
	for (int i = 0; i < r2 - r1 + 1; i++) {
		for (int j = 0; j < c2 - c1 + 1; j++) {
			num[i][j] = w(map[i][j]);
			max_num = max(max_num, num[i][j]);
		}
	}
}

int main() {
	cin >> r1 >> c1 >> r2 >> c2;

	simul();

	for (int i = 0; i < r2 - r1 + 1; i++) {
		for (int j = 0; j < c2 - c1 + 1; j++) {
			int tmp = max_num - num[i][j];
			while (tmp--) {
				cout << ' ';
			}
			cout << map[i][j] << ' ';
		}
		puts("");
	}
	
	return 0;
}