BOJ 23291번: 어항 정리

문제

문제 바로가기> BOJ 23291번: 어항 정리

23291번: 어항 정리

 

풀이

어항을 쌓는 부분을 제외한 나머지 부분의 구현은 평이한 편이다..

다만 어항 쌓느라 1시간 넘게 쓴 것 같다 ...

어항 쌓기 규칙을 찾아주는 게 어려웠다 ... 조금 .... 많이 ...

 

💡 어항 쌓기 규칙

총 5가지 변수를 이용해서 규칙을 찾았다.
cnt : 그냥 1, 2, 3, 4, ... monotonic 하게 증가
idx : cnt가 짝수인 경우 1 증가한다.
        pivot이 증가할 때 pivot+=idx 형식으로 증가하는 패턴을 띄므로
        이 때 사용하기 위해서 필요하다.
pivot : 어항의 시작점이다. 처음엔 당연히 0, 한번 쌓고나면 1 .... 
y : 쌓을 어항의 행 개수
x : 쌓을 어항의 열 개수

✅ 쌓을 어항의 끝 컬럼부터 차례대로 쌓아 주어야 한다. 
      끝 컬럼이 N-2 row 가 되므로!!
      따라서 for(col) { for(row) .. } 형태의 이중 반복문을 돌아주면 된다!
✅ map[N - 1 - c - 1][pivot + x + r] = map[N - 1 - r][pivot + x - c - 1]
      위 부분이 어항을 쌓는 부분의 규칙이다.
      ☑️ 열 : pivot + x + r ( 마지막 row 부터 위로 가면서 col으로 쌓인다. )
      ☑️ 행 : N - 1 - c - 1 ( 마지막 col 부터 역방향으로 가면서 row로 쌓인다.)

✅ 처음에 c=0~x , r=0~y 형태로 반복문을 돌지 않고,
      바로 값을 넣어서 어항을 쌓으려고 했지만,
      쌓을 어항 내에서 규칙을 만들 때,
      monotonic 하게 증가하는 변수가 필요했고,
      따라서 위와 같이 바꿔주었다.

cnt	idx	pivot	y	x
1	0	0	1	1
2	1	1	2	1
3	1	2	2	2
4	2	4	3	2
5	2	6	3	3
...	...	...	...	...

 

#include<iostream>
#include<algorithm>
#define EMPTY 0
#define MAX 101
#define INF 1000001
using namespace std;

int N, K;
int map[MAX][MAX];
int tmpMap[MAX][MAX];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };

void input() {
	cin >> N >> K;
	for (int x = 0; x < N; x++) cin >> map[N-1][x];
}

void copy_and_init() {
	for (int y = 0; y < MAX; y++) {
		for (int x = 0; x < MAX; x++) {
			map[y][x] += tmpMap[y][x];
			tmpMap[y][x] = EMPTY;
		}
	}
}

// 물고기가 가장 많이 들어있는 어항과 
// 가장 적게 들어있는 어항의 물고기 수 차이가 K 이하
bool check() {
	int minFish=INF, maxFish=0;
	for (int x = 0; x < N; x++) {
		minFish = min(minFish, map[N-1][x]);
		maxFish = max(maxFish, map[N-1][x]);
	}
	return (maxFish - minFish) > K;
}

void add_fish() { // 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣음
	int minFish = INF;
	for (int x = 0; x < N; x++) 
		minFish = min(minFish, map[N-1][x]);
	for (int x = 0; x < N; x++) {
		if (map[N-1][x] == minFish) map[N-1][x]++;
	}
}

void rotate90() {
	int pivot = 0, idx = 0, y = 1, x = 1;
	for (int cnt = 1; ; cnt++) {
		if (cnt % 2 == 0) idx++; pivot += idx;
		if (pivot + y + x -1 >= N) break; // 더 이상 쌓을 수 없는 경우

		for (int c = 0; c < x; c++) {
			for (int r = 0; r < y; r++) {
				map[N - 1 - c - 1][pivot + x + r] = map[N - 1 - r][pivot + x - c - 1];
				map[N - 1 - r][pivot + x - c - 1] = EMPTY;
			}
		}
		cnt % 2 ? y++ : x++;
	}
}

void control() { // 물고기 수 조절
	for (int y = 0; y < MAX; y++) {
		for (int x = 0; x < MAX; x++) {
			if (map[y][x] == EMPTY) continue;
			for (int d = 0; d < 4; d += 2) { // 상좌만 탐색 (겹치는 경우 제외)
				int ny = y + dy[d];
				int nx = x + dx[d];
				if (ny < 0 || ny >= MAX || nx < 0 || nx >= MAX) continue;
				if (map[ny][nx] == EMPTY) continue;
				int diff = abs(map[y][x] - map[ny][nx])/5;
				if (diff == 0) continue;

				if (map[y][x] < map[ny][nx]) {
					tmpMap[y][x] += diff;
					tmpMap[ny][nx] -= diff;
				}
				else {
					tmpMap[y][x] -= diff;
					tmpMap[ny][nx] += diff;
				}
			}
		}
	}
	copy_and_init();
}

void flatten() {
	int nx = 0;
	for (int x = 0; x < N; x++) {
		for (int y = N-1; y >= 0; y--) {
			if (map[y][x] == 0)break;
			tmpMap[N-1][nx++] = map[y][x];
			map[y][x] = EMPTY;
		}
	}
	copy_and_init();
}

void rotate180() { // 180도 회전 시킨 다음, 오른쪽 N/2개의 위에 놓음 (2번)
	int mid = N / 2;
	for (int x = 0; x < mid; x++) {
		map[N - 2][N - 1 - x] = map[N - 1][x];
		map[N - 1][x] = EMPTY;
	}
	for (int x = mid; x < mid + mid / 2; x++) {
		map[N - 3][N - 1 - x + mid] = map[N - 2][x];
		map[N - 2][x] = EMPTY;
		map[N - 4][N - 1 - x + mid] = map[N-1][x];
		map[N - 1][x] = EMPTY;
	}
}

void solution() {
	int ans = 0;
	while (check()) { // 어항을 한 번 정리하는 과정
		add_fish(); // 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣음
		rotate90(); // 어항을 쌓음
		control(); // 어항에 있는 물고기의 수를 조절
		flatten(); // 다시 어항을 바닥에 일렬로 놓음
		rotate180(); // 가운데를 중심으로 왼쪽 N/2개를 공중 부양
		control(); // 다시 위에서 한 물고기 조절 작업을 수행
		flatten(); // 다시 어항을 바닥에 일렬로 놓음
		ans++;
	}
	cout << ans;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	input();
	solution();
}