kunkunwoo@blog:~$ 거누권의 생각깜지

백준 17822번 _ 원판 돌리기

· 배운 것 · 10분 읽기

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

17822번: 원판 돌리기

풀이방법

1. 원판을 회전시킨다.
2. 인접한수가 있는지 확인하고 있다면 -1로 바꿔준다
3. 인접한수가 없다면 평균을 구해 평균보다 큰수는 +1, 작은수는 -1, 같은수는 그대로 바꿔준다.

위의 세개를 연속해서 수행하면된다. 구현자체는 어렵지않으니 내가 삽질했던 사항만 적어볼까한다.

틀렸던 부분

원판을 회전시킬 x의 배수를 구할때

void rotate(int x, int d, int k)
{
	for (int i = x; i <= N; i +=x)// i*=2가 아니라 i+=x가 배수를 표현한다
	{
		if (d == 0)
			CR(i - 1, k);
		else if (d == 1)
			CCR(i - 1, k);
	}
}

인덱스로 접근하지 않아 틀린 부분

틀렸던 코드

cin >> N >> M >> T;
int value;
roundPlant.resize(N + 2);
for (int i = 0; i < N; i++)
{
	for (int j = 0; j < M; j++)
	{
		cin >> value;
		roundPlant[i].push_back(value);
	}
}
queue<int> que;
for (int i = 0; i < M; i++)
	que.push(roundPlant[n][i]);

맞은 코드

cin >> N >> M >> T;
int value;
roundPlant.resize(N + 2);
for (int i = 0; i < N; i++)
	roundPlant[i].resize(M + 1);//추가

for (int i = 0; i < N; i++)
{
	for (int j = 0; j < M; j++)
	{
		cin >> value;
		roundPlant[i][j] = value;//고침
	}
}
queue<int> que;
for (int i = 0; i < M; i++)		//i<(int)roundPlant.size()였음
	que.push(roundPlant[n][i]);

사실 이 부분은 아직까지도 문제가 없다고 생각하는데 왜 틀린지 잘 모르겠다.
roundPlant[i]에 push_back으로 넣어 roundPlant.size()를 써도 문제가 없다고 생각했는데 틀렸었다.
하지만, 이것때문에 약 2시간동안 전체코드를 수십번 읽으며 개고생했으므로 미리공간을 만들고 인덱스로 접근하는 식으로 코딩을 해야겠다.

전체코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

vector<vector<int>> roundPlant;
int N, M, T;

void plusOrMinus(double average)
{
	int averMultiply = (average * 1000.0);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (roundPlant[i][j] == -1)
				continue;
			if ((roundPlant[i][j] * 1000) > averMultiply)
				roundPlant[i][j] --;
			else if ((roundPlant[i][j] * 1000) < averMultiply)
				roundPlant[i][j] ++;
		}
	}
}

double getAverage()
{
	double total = 0;
	double cnt = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (roundPlant[i][j] == -1)
				continue;
			total += roundPlant[i][j];
			cnt++;
		}
	}
	return total / cnt;
}

int checkAndChangePlant()
{
	int cnt = 0;
	vector<vector<int>>calRoundPlant = roundPlant;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			int value = roundPlant[i][j];
			if (value == -1)
				continue;
			if (j == 0)
			{
				if (calRoundPlant[i][1] == value) {
					calRoundPlant[i][1] = -1; cnt++;
				}
				if (calRoundPlant[i][M - 1] == value) {
					calRoundPlant[i][M - 1] = -1; cnt++;
				}
			}
			else if (j == M - 1)
			{
				if (calRoundPlant[i][M - 2] == value) {
					calRoundPlant[i][M - 2] = -1; cnt++;
				}
				if (calRoundPlant[i][0] == value) {
					calRoundPlant[i][0] = -1; cnt++;
				}
			}
			else
			{
				if (calRoundPlant[i][j - 1] == value) {
					calRoundPlant[i][j - 1] = -1; cnt++;
				}
				if (calRoundPlant[i][j + 1] == value) {
					calRoundPlant[i][j + 1] = -1; cnt++;
				}
			}

			if (i == 0)
			{
				if (calRoundPlant[1][j] == value) {
					calRoundPlant[1][j] = -1; cnt++;
				}
			}
			else if (i == N - 1)
			{
				if (calRoundPlant[N - 2][j] == value) {
					calRoundPlant[N - 2][j] = -1; cnt++;
				}
			}
			else
			{
				if (calRoundPlant[i - 1][j] == value) {
					calRoundPlant[i - 1][j] = -1; cnt++;
				}
				if (calRoundPlant[i + 1][j] == value) {
					calRoundPlant[i + 1][j] = -1; cnt++;
				}
			}
		}
	}
	roundPlant = move(calRoundPlant);
	return cnt;
}

void CCR(int n, int k)
{
	queue<int> que;
	for (int i = 0; i < M; i++)
		que.push(roundPlant[n][i]);

	for (int i = 0; i < k; i++)
	{
		que.push(que.front());
		que.pop();
	}

	vector<int> result;
	while (!que.empty())
	{
		result.push_back(que.front());
		que.pop();
	}

	roundPlant[n] = move(result);
}

void CR(int n, int k)
{
	//M - k번 ccr하면 k번 cr이랑 같음
	int nk = M - k;
	CCR(n, nk);
}

void rotate(int x, int d, int k)
{
	for (int i = x; i <= N; i +=x)
	{
		if (d == 0)
			CR(i - 1, k);
		else if (d == 1)
			CCR(i - 1, k);
	}
}

void InputAndSolve()
{
	cin >> N >> M >> T;
	int value;
	roundPlant.resize(N + 2);
	for (int i = 0; i < N; i++)
		roundPlant[i].resize(M + 1);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> value;
			roundPlant[i][j] = value;
		}
	}
	int x, d, k;
	for (int i = 0; i < T; i++)
	{
		cin >> x >> d >> k;
		k %= M;
		//여기서 rotate
		rotate(x, d, k);
		//이후 체크
		if (checkAndChangePlant() == 0)
		{
			//average 구해서 +1 -1해야함
			plusOrMinus(getAverage());
		}
	}
}

int countPlant()
{
	int cnt = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (roundPlant[i][j] == -1)
				continue;
			cnt += roundPlant[i][j];
		}
	}
	return cnt;
}

int main()
{
	InputAndSolve();
	cout << countPlant();
	return 0;
}

후기

구현은 오래걸리지 않았는데 저 위의 사항들로 인해 꽤나 오랜시간을 투자해 풀었다.