어항 정리 (feat. 백준, 23291번)

어항 정리
https://www.acmicpc.net/problem/23291

23291번: 어항 정리

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/23291
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int N, K;
int arr[101][101];
int tmp[101][101];
int dx[4], dy[4];
void add_fish() {
	auto min_fish = *min_element(arr[0], arr[0] + N);
	for (auto idx = 0; idx < N; ++idx)
		if (arr[0][idx] == min_fish)		++arr[0][idx];
}
void change_array(int& width, int& height) {
	for (int ix = 0, iy; ix < height; ++ix)
		for (iy = 0; iy < width; ++iy)
			tmp[iy][ix] = arr[ix][width - iy - 1];
}
void stack() {
	auto width = 1, height = 1, n = N;
	while ((n - width) >= height) {
		change_array(width, height);
		for (auto idx = width; idx < N; ++idx)
			arr[0][idx - width] = arr[0][idx], arr[0][idx] = 0;
		for (auto idx = 0; idx < width; ++idx)
			memcpy(arr[idx + 1], tmp[idx], sizeof(int) * height);
		n -= width;
		if (width == height)		++height;
		else						++width;
	}
}
void organize() {
	int temp[101][101] = { 0 };
	for(int ix = 0, iy, i, nx, ny, offset; ix < N; ++ix)
		for(iy = 0; iy < N && arr[ix][iy] != 0; ++iy)
			for (i = 0; i < 4; ++i) {
				nx = ix + dx[i], ny = iy + dy[i];
				if (0 <= nx && nx < N && 0 <= ny && ny < N && arr[nx][ny] != 0) {
					offset = (arr[ix][iy] - arr[nx][ny]) / 5;
					if (offset > 0) {
						if (arr[ix][iy] > arr[nx][ny])			temp[ix][iy] -= offset, temp[nx][ny] += offset;
						else if (arr[ix][iy] < arr[nx][ny])		temp[nx][ny] -= offset, temp[ix][iy] += offset;
					}
				}
			}
	for (int ix = 0, iy; ix < N; ++ix)
		for (iy = 0; iy < N; ++iy)
			arr[ix][iy] += temp[ix][iy];
}
void arrange() {
	int index = 0;
	for (int iy = 0, ix; iy < N; ++iy)
		for (ix = 0; ix < N; ++ix) {
			if (arr[ix][iy] == 0)	break;
			tmp[0][index++] = arr[ix][iy];
		}
	memset(arr, 0, sizeof(int) * 101 * 101);
	memcpy(arr[0], tmp[0], sizeof(int) * index);
}
void fold()
{
	// 첫번째
	for (auto idx = 0; idx < N / 2; ++idx)
		tmp[0][N / 2 - 1 - idx] = arr[0][idx], arr[0][idx] = arr[0][N / 2 + idx], arr[0][N / 2 + idx] = 0;
	memcpy(arr[1], tmp[0], sizeof(int) * N / 2);

	// 두번째
	for (int ix = 0, iy; ix < 2; ++ix)
		for (iy = 0; iy < N / 4; ++iy)
			arr[3 - ix][N / 4 - 1 - iy] = arr[ix][iy];
	for (int ix = 0, iy; ix < 2; ++ix)
		for (iy = 0; iy < N / 4; ++iy)
			arr[ix][iy] = arr[ix][N / 4 + iy], arr[ix][N / 4 + iy] = 0;
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
	for (int ix = 0, iy; ix < 101; ++ix)
		for (iy = 0; iy < 101; ++iy)
			arr[ix][iy] = 0;
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;

	cin >> N >> K;
	for (auto idx = 0; idx < N; ++idx)
		cin >> arr[0][idx];

	auto try_count = 1;
	while (true) {
		add_fish();
		stack();
		organize();
		arrange();
		fold();
		organize();
		arrange();

		if ((*max_element(arr[0], arr[0] + N) - *min_element(arr[0], arr[0] + N)) <= K)
			break;
		++try_count;
	}

	cout << try_count << endl;
	return 0;
}
// *&)*@*

시간이 너무 오래 걸렸습니다. 때려칠까 하다가 시작한게 아까워서 끝까지 했습니다. 2시간이나 걸렸네요... 무식하게 풀었습니다.

1. 첫번째 어항 정리는 김밥만들기처럼 동글동글 말아 올라가는 형태입니다. 여기서 처음은 w=1,h=1이고 이렇게 말면 h+=1을 해줍니다. 그리고 다음 말기는 w=1, h=2이고 이렇게 말면 w+=1을 해줍니다. 이런 규칙에 의해서 다음번 말이때 N - width가 height보다 작으면 그만 말아줘야 합니다.
2. 두번째 어항 정리는 딱 2번만 폴딩하면 됩니다. 따라서 첫번째 폴딩 결과의 높이는 항상 2이고, 두번째 폴딩 결과의 높이는 항상 4 입니다. 이 정보를 토대로 for문을 작성했습니다.