어항 정리 C++

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

23291번: 어항 정리

#include <iostream>
#include <vector>

using namespace std;
int n, k;
vector<int> linefish;
vector<vector<int>> fish;
int answer = 0;

void PlusFish() {
	int minvalue = 20000;
	vector<int> index;

	for (int i = 0; i < linefish.size(); i++) {
		if (linefish[i] < minvalue) {
			minvalue = linefish[i];
			index.clear();
			index.push_back(i);
		}

		else if (linefish[i] == minvalue) {
			index.push_back(i);
		}
	}

	for (int i = 0; i < index.size(); i++) {
		linefish[index[i]] += 1;
	}
}

bool CheckFinish() {
	int minvalue = 20000;
	int maxvalue = -1;

	for (int i = 0; i < linefish.size(); i++) {
		if (linefish[i] < minvalue) {
			minvalue = linefish[i];
		}

		if (linefish[i] > maxvalue) {
			maxvalue = linefish[i];
		}
	}

	int v = maxvalue - minvalue;
	if (v <= k)	return false;
	else return true;
}

void PushFish() {
	fish.clear();
	fish.push_back(linefish);
}

void ClearFish2() {
	vector<vector<int>> tmp;

	tmp.push_back({ linefish[0] });
	for (int i = 0; i < linefish.size() - 2; i++) {
		tmp[0].push_back(-1);
	}
	linefish.erase(linefish.begin());
	tmp.push_back(linefish);

	fish = tmp;
}

void ClearFish() {
	int height; //가로 길이로 변환됨(이게 바닥 어항의 너비보다 작거나 같아야함
	int width; //높이로 추가됨
	int origin = linefish.size(); //원래 일직선 어항의 길이
	vector<vector<int>> tmp;

	while (true) {
		int sz = origin;
		for (int i = 0; i < fish[0].size(); i++) {
			if (fish[0][i] == -1) {
				sz = i;
				break;
			}
		}
		height = fish.size();
		width = sz;

		if (height > origin - width)	break;

		//공중부양 시킬 어항
		vector<vector<int>> move;
		move.resize(height);
		for (int i = 0; i < height; i++) {
			for (int j = 0; j < width; j++) {
				move[i].push_back(fish[i][j]);
			}
		}

		//90도 회전
		vector<vector<int>> move_tmp;
		move_tmp.resize(move[0].size());
		int index_i = 0, index_j = 0;
		for (int j=0; j<width; j++){
			for (int i = height - 1; i >= 0; i--) {
				move_tmp[index_i].push_back(move[i][j]);
			}
			index_i++;
		}

		//어항에 쌓기
		vector<int> temp;
		for (int i = width; i < linefish.size(); i++) {
			temp.push_back(linefish[i]);
		}
		move_tmp.push_back(temp);

		//비어있는 곳은 -1로 세팅하기
		int maxsize = move_tmp[move_tmp.size() - 1].size();
		for (int i = 0; i < move_tmp.size() - 1; i++) {
			for (int j = 0; j < maxsize; j++) {
				if (move_tmp[i].size() <= j)	move_tmp[i].push_back(-1);
			}
		}

		//origin 크기 변경
		origin = move_tmp[0].size();

		fish.clear();
		fish = move_tmp;

		for (int i = 0; i < width; i++)	linefish.erase(linefish.begin());
	}
}

void ChangeFish() {
	vector<vector<int>> tmp = fish;

	for (int i = 0; i < fish.size(); i++) {
		for (int j = 0; j < fish[0].size(); j++) {
			//오른쪽
			int movei = i;
			int movej = j + 1;
			if (movei >= 0 && movei < fish.size() && movej >= 0 && movej < fish[0].size()) {
				if (tmp[movei][movej] != -1 && tmp[i][j] != -1) {
					if (tmp[i][j] > tmp[movei][movej]) {
						int value = (tmp[i][j] - tmp[movei][movej]) / 5;
						fish[i][j] -= value;
						fish[movei][movej] += value;
					}
					else if (tmp[i][j] < tmp[movei][movej]) {
						int value = (tmp[movei][movej] - tmp[i][j]) / 5;
						fish[i][j] += value;
						fish[movei][movej] -= value;
					}
				}
			}

			//아래
			movei = i + 1;
			movej = j;
			if (movei >= 0 && movei < fish.size() && movej >= 0 && movej < fish[0].size()) {
				if (tmp[movei][movej] != -1 && tmp[i][j]!= -1) {
					if (tmp[i][j] > tmp[movei][movej]) {
						int value = (tmp[i][j] - tmp[movei][movej]) / 5;
						fish[i][j] -= value;
						fish[movei][movej] += value;
					}
					else if (tmp[i][j] < tmp[movei][movej]) {
						int value = (tmp[movei][movej] - tmp[i][j]) / 5;
						fish[i][j] += value;
						fish[movei][movej] -= value;
					}
				}
			}
		}
	}
}

void MakeLine() {
	linefish.clear();

	for (int j = 0; j < fish[0].size(); j++) {
		for (int i = fish.size() - 1; i >= 0; i--) {
			if (fish[i][j] != -1) {
				linefish.push_back(fish[i][j]);
			}
		}
	}
}

void DivideMiddle() {
	int sz = linefish.size();
	fish.clear();

	fish.resize(2);
	for (int i = sz/2-1; i >= 0; i--) {
		fish[0].push_back(linefish[i]);
	}

	for (int i = sz / 2; i < linefish.size(); i++) {
		fish[1].push_back(linefish[i]);
	}

	vector<vector<int>> tmp2;
	tmp2.resize(2);
	int index = 0;
	for (int i = 1; i >= 0; i--) {
		for (int j = fish[0].size() / 2 - 1; j >= 0; j--) {
			tmp2[index].push_back(fish[i][j]);
		}
		index++;
	}

	for (int i = 0; i < fish.size(); i++) {
		vector<int> tp;
		for (int j = fish[0].size() / 2; j < fish[0].size(); j++) {
			tp.push_back(fish[i][j]);
		}
		tmp2.push_back(tp);
	}

	fish.clear();
	fish = tmp2;
}

int main(void) {
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		linefish.push_back(num);
	}

	while (CheckFinish()) {
		answer++;
		PlusFish();
		PushFish();
		ClearFish2();
		ClearFish();
		ChangeFish();
		MakeLine();
		DivideMiddle();
		ChangeFish();
		MakeLine();
	}

	cout << answer << endl;
}