Sam의 피자 학교

Simulation

평균 : 180'

---

sol : 366' 38''

• 수행 시간 : 24ms
• 메모리 : 0MB

Learnings

• 애매한 로직은 피를 부른다.
• 어려운 건 잘 구현해놓고 가장 쉬운 로직을 틀려서 디버깅을 3시간 넘게 했다.
• 그래도 오답 원인을 찾아서 해결해서 다행.

#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_N 100

int n, k;
int diff;
int turn;
int dowGrid[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
// 상, 좌
int ds[2][2] = { {-1, 0}, {0, -1} };

// 각 열 벡터
vector<int> d2_dow[MAX_N];

void Debug() {
	cout << endl << "DEBUG" << endl;
	for (int j = 0; j < n; j++) {
		for (int i = 0; i < d2_dow[j].size(); i++) {
			cout << d2_dow[j][i] << ' ';
		}
		cout << endl;
	}
	cout << endl;
}

void Debug_2(int g[MAX_N][MAX_N]) {
	cout << endl << "dow GRID" << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << g[i][j] << ' ';
		}
		cout << endl;
	}
	cout << endl;
}

void InitDowGrid() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dowGrid[i][j] = 0;
		}
	}
}

void InitVisited() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			visited[i][j] = false;
		}
	}
}

void DupGrid(int from[MAX_N][MAX_N], int to[MAX_N][MAX_N]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			to[i][j] = from[i][j];
		}
	}
}

void Init() {
	cin >> n >> k;
	for (int j = 0; j < n; j++) {
		int dow;
		cin >> dow;
		d2_dow[j].push_back(dow);
	}
}

bool CheckFin() {
	int minD = INT_MAX, maxD = INT_MIN;
	for (int j = 0; j < n; j++) {
		if (d2_dow[j][0] > maxD) maxD = d2_dow[j][0];
		if (d2_dow[j][0] < minD) minD = d2_dow[j][0];
	}

	if (maxD - minD <= k) return true;
	else return false;
}

void PutFlour() {
	int minD = INT_MAX;
	vector<int> candidates;
	for (int j = 0; j < n; j++) {
		if (d2_dow[j][0] < minD) {
			minD = d2_dow[j][0];
			candidates.clear();
			candidates.push_back(j);
		}
		else if (d2_dow[j][0] == minD) {
			candidates.push_back(j);
		}
	}

	for (int i = 0; i < candidates.size(); i++) {
		d2_dow[candidates[i]][0]++;
	}
}

bool BottomWider() {
	int bottomLen = 1, upperLen = 0;
	for (int j = 0; j < n; j++) {
		if (d2_dow[j].empty()) continue;

		upperLen = d2_dow[j].size();
		break;
	}

	for (int j = 0; j < n; j++) {
		if (d2_dow[j].size() != 1) continue;

		bottomLen = n - j;
		break;
	}

	return (bottomLen >= upperLen);
}

int FindCenter() {
	for (int j = 0; j < n - 1; j++) {
		if (d2_dow[j].size() == 0) continue;
		if (d2_dow[j].size() > d2_dow[j + 1].size()) {
			return j;
		}
	}
	return 0;
}

void RollProcess(int cj) {
	int rollSize = d2_dow[cj].size();

	for (int j = cj; j >= 0; j--) {
		if (d2_dow[j].empty()) break;

		for (int i = 0; i < rollSize; i++) {
			d2_dow[cj + rollSize - i].push_back(d2_dow[j].back());
			d2_dow[j].pop_back();
		}
	}
}

void Roll() {
	while (true) {
		if (!BottomWider()) break;

		// 1. 말아주는 중심점 찾기 (중심점 좌측 열 리턴)
		int cen_j = FindCenter();

		// 2. 중심점 좌측을 시계 방향 90도 회전해서 변 길이만큼 우측 위로 쌓기
		RollProcess(cen_j);
	}
}

bool InGrid(int i, int j) {
	return 0 <= i && i < n && 0 <= j && j < n;
}

void Press() {
	// 1. 골고루 섞기
	InitDowGrid();
	int tempGrid[MAX_N][MAX_N];

	for (int j = 0; j < n; j++) {
		if (d2_dow[j].empty()) continue;
		for (int i = 0; i < d2_dow[j].size(); i++) {
			dowGrid[n - 1 - i][j] = d2_dow[j][i];
		}
	}

	DupGrid(dowGrid, tempGrid);

	for (int i = n - 1; i >= 0; i--) {
		bool rowEmpty = true;
		for (int j = n - 1; j >= 0; j--) {
			if (dowGrid[i][j] > 0) {
				rowEmpty = false;

				for (int d = 0; d < 2; d++) {
					int ni = i + ds[d][0], nj = j + ds[d][1];
					if (InGrid(ni, nj) && dowGrid[ni][nj] > 0) {
						int diff = abs(dowGrid[ni][nj] - dowGrid[i][j]) / 5;
						if (dowGrid[ni][nj] > dowGrid[i][j]) {
							tempGrid[ni][nj] -= diff;
							tempGrid[i][j] += diff;
						}
						else if (dowGrid[ni][nj] < dowGrid[i][j]) {
							tempGrid[ni][nj] += diff;
							tempGrid[i][j] -= diff;
						}
					}
				}
			}
		}

		if (rowEmpty) break;
	}

	DupGrid(tempGrid, dowGrid);

	// 2. 1차원화
	for (int j = 0; j < n; j++) d2_dow[j].clear();

	for (int j = 0; j < n; j++) {
		bool filled = false;
		for (int gj = 0; gj < n; gj++) {
			for (int gi = n - 1; gi >= 0; gi--) {
				if (dowGrid[gi][gj] > 0) {
					d2_dow[j].push_back(dowGrid[gi][gj]);
					dowGrid[gi][gj] = 0;
					filled = true;
					break;
				}
			}
			if (filled) break;
		}
	}
}

void FoldTwice() {
	int half = n / 2;
	for (int j = 0; j < half; j++) {
		d2_dow[n - 1 - j].push_back(d2_dow[j].back());
		d2_dow[j].pop_back();
	}

	int q3 = n / 2 + n / 4;
	for (int j = half; j < q3; j++) {
		for (int elem = 0; elem < 2; elem++) {
			d2_dow[n - 1 - (j - half)].push_back(d2_dow[j].back());
			d2_dow[j].pop_back();
		}
	}
}

int main() {
	Init();

	while (true) {
		turn++;
		PutFlour();

		Roll();

		Press();

		FoldTwice();

		Press();

		// 6. CheckFin
		if (CheckFin()) break;
	}

	cout << turn;

	return 0;
}