[백준]23291 어항정리

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

23291번: 어항 정리

 

 

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

int N, K;
int ret = 0;

void printVector(vector<int> v)
{
	for (int i = 0; i < N; i++)
		cout << v[i] << "	";
	cout << endl;
}
void print2Vector(vector<vector<int>> v)
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			cout << v[i][j] << "	";
		cout << endl;
	}
	cout << endl;
}

void firstClean(vector<int> &v)
{
	int min = 10001;
	vector<int> minIndex;
	for (int i = 0; i < N; i++)
	{
		if (v[i] <= min)
		{
			min = v[i];
			minIndex.push_back(i);
			for (int j = 0; j < minIndex.size(); j++)
			{
				if (v[minIndex[j]] > min)
				{
					minIndex.erase(minIndex.begin() + j);
				}
				else continue;
			}
		}
		else continue;
	}

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

void secClean(vector<int>t, vector<vector<int>>& v)
{
	vector<vector<int>> newMap(N, vector<int>(N, -1));
	int moveNum = 0, moveCnt = 0;
	int col = 0, row = 0;

	for (int i = 0; i < N; i++)
	{
		v[0][i] = t[i];
		newMap[0][i] = t[i];
	}

	bool endFlag = true;
	int endRow = 1;

	while (endFlag) {

		if (!(moveCnt % 2)) {
			moveNum++;
			col = moveNum, row = endRow;
		}
		else col = moveNum + 1, row = endRow;

		int y = 0, x = row;
		//cout << "y: " << y << " x: " << x << endl;
		
			for (int i = 0; i < col; i++)
		{
			if (!endFlag) break;
			for (int j = 1; j <= row; j++)
			{
				int sy = y + i, sx = x - j;
				int ny = y + j, nx = x + i;

				if (ny >= N || nx >= N || sx < 0)
				{
					endFlag = false;
					break;
				}

				newMap[ny][nx] = v[sy][sx];
				newMap[sy][sx] = -1;
			}
		}
		if (!endFlag) break;

		v = newMap;
		endRow += col;
		moveCnt++;
	}
}

void controlMap(vector<vector<int>>& v)
{
	vector<vector<int>> newMap(N, vector<int>(N, -1));
	newMap = v;

	int _y[] = { 1,0 };
	int _x[] = { 0,1 };

	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			//cout << "y: " << y << " x: " << x << endl;
			if (v[y][x] == -1) continue;
			for (int d = 0; d < 2; d++)
			{
				int ny = y + _y[d], nx = x + _x[d];
				//cout << "ny: " << ny << " nx: " << nx << endl;
				if (ny >= N || nx >= N) continue;
				if (v[ny][nx] == -1)continue;

				int diff = v[y][x] - v[ny][nx];
				if (diff >= 5) {
					newMap[y][x]-= (abs(diff) / 5);
					newMap[ny][nx] += (abs(diff) / 5);
				}
				else if (diff <= -5)
				{
					newMap[y][x] += int(abs(diff) / 5);
					newMap[ny][nx] -= int(abs(diff) / 5);
				}


			}
		}
	}
	v = newMap;
	
}

void arrangeMap(vector<int>&t, vector<vector<int>>& v)
{
	int idx = 0;
	for (int x = 0; x < N; x++)
	{
		for (int y = 0; y < N; y++)
		{
			if (v[y][x] != -1)  t[idx++] = v[y][x];
		}
	}
}

vector<vector<int>> levitation(vector<int> t)
{
	vector<vector<int>> newMap(N,vector<int>(N));
	fill(newMap.begin(), newMap.end(), vector<int>(N,-1));

	for (int i = 0; i < N; i++)
	{
		newMap[0][i] = t[i];
	}
	
	//N/2 levitation
	int col = 0, row = N / 2;
	for (int j = 1; j <= N / 2; j++)
	{
		int sy = col, sx = row - j;
		int ny = 1, nx = row + j - 1;
		if (sx < 0 || nx >= N) break;
		newMap[ny][nx] = newMap[sy][sx];
		newMap[sy][sx] = -1;
	}

	//N/4 levitaion
	col = 1, row = N / 2 + N / 4 - 1;
	pair<int, int> change = make_pair(col + 1, row + 1);
	for (int i = 0; i <= 1; i++) {
		for (int j = 0; j < N / 4; j++) 
		{
			int sy = col - i, sx = row - j;
			int ny = change.first + i, nx = change.second + j;
			newMap[ny][nx] = newMap[sy][sx];
			newMap[sy][sx] = -1;
		}
	}

	return newMap;
}

int main()
{
	cin >> N >> K;

	vector<int> tank(N, 0);
	vector<vector<int>> map(N, vector<int>(N,-1));

	for (int i = 0; i < N; i++)
	{
		cin >> tank[i];
	}

	while (1) {
		int min = *min_element(tank.begin(), tank.end());
		int max = *max_element(tank.begin(), tank.end());

		if (max - min <= K) break;

		firstClean(tank);
		secClean(tank, map);
		controlMap(map);
		arrangeMap(tank, map);
		map = levitation(tank);
		controlMap(map);
		arrangeMap(tank, map);

		ret++;
	}
	cout << ret;
	return 0;
}

 

TestCase 10개 모두 통과하는데 틀렸습니다!