원판 돌리기 (feat. 백준, 17822번)

원판 돌리기
https://www.acmicpc.net/problem/17822

17822번: 원판 돌리기

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/17822
#include <iostream>
#include <cstring>
using namespace std;

int N, M, T;
int arr[51][51];
int tmp[51][51];

void shift_stencil(int(*tmp), const int& d, const int& k)
{
	if (d == 0)	// 시계방향
		for (int idx = 0, temp; idx < k; ++idx)
			temp = tmp[M - 1], memmove(tmp + 1, tmp, sizeof(int) * (M - 1)), tmp[0] = temp;
	else		// 반시계방향
		for (int idx = 0, temp; idx < k; ++idx)
			temp = tmp[0], memmove(tmp, tmp + 1, sizeof(int) * (M - 1)), tmp[M - 1] = temp;
}

void turn_stencil(const int& x, const int& d, const int& k)
{
	for (auto ix = 1; ix <= N; ++ix)
		if ((ix % x) == 0)
			shift_stencil(arr[ix - 1], d, k);

	for (int ix = 0, iy; ix < N; ++ix)
		for (iy = 0; iy < M; ++iy) {
			if (arr[ix][iy] == 0)		continue;
			if (0 < ix && ix < (N - 1)) {
				if (arr[ix][iy] == arr[ix - 1][iy])
					tmp[ix][iy] = tmp[ix - 1][iy] = -1;
				if (arr[ix][iy] == arr[ix + 1][iy])
					tmp[ix][iy] = tmp[ix + 1][iy] = -1;
			}
			else if (ix == 0) {
				if (arr[ix][iy] == arr[ix + 1][iy])
					tmp[ix][iy] = tmp[ix + 1][iy] = -1;
			}
			else {
				if (arr[ix][iy] == arr[ix - 1][iy])
					tmp[ix][iy] = tmp[ix - 1][iy] = -1;
			}
			if (arr[ix][iy] == arr[ix][(M + iy - 1) % M])
				tmp[ix][iy] = tmp[ix][(M + iy - 1) % M] = -1;
			if (arr[ix][iy] == arr[ix][(M + iy + 1) % M])
				tmp[ix][iy] = tmp[ix][(M + iy + 1) % M] = -1;
		}

	bool changed = false;
	for (int ix = 0, iy; ix < N; ++ix)
		for (iy = 0; iy < M; ++iy)
			if (tmp[ix][iy] == -1)		changed = true, arr[ix][iy] = tmp[ix][iy] = 0;

	if (!changed) {
		double sum = 0.0;
		auto count = 0;
		for (int ix = 0, iy; ix < N; ++ix)
			for (iy = 0; iy < M; ++iy)
				if (arr[ix][iy] != 0)	sum += arr[ix][iy], ++count;
		if (count > 0) {
			sum /= count;
			for (int ix = 0, iy; ix < N; ++ix)
				for (iy = 0; iy < M; ++iy)
					if (arr[ix][iy] != 0)
						if (arr[ix][iy] > sum)			--arr[ix][iy];
						else if (arr[ix][iy] < sum)		++arr[ix][iy];
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
	cin >> N >> M >> T;
	for (int ix = 0, iy; ix < N; ++ix)
		for (iy = 0; iy < M; ++iy)
			cin >> arr[ix][iy], tmp[ix][iy] = 0;
	for (int t = 0, x, d, k; t < T; ++t)
		cin >> x >> d >> k, turn_stencil(x, d, k);
	auto result = 0;
	for (int ix = 0, iy; ix < N; ++ix)
		for (iy = 0; iy < M; ++iy)
			result += arr[ix][iy];
	cout << result << endl;
	return 0;
}
// *&)*@*

1. 원판기준 북쪽을 배열의 시작으로 보았습니다.
2. 배열을 한칸씩 이동시키는 방법은 for문도 있지만 memmove를 사용하면 쉽게 해결됩니다.
3. 시간을 가장 많이 소비한 부분입니다. 56%에서 실패가 발생했습니다. 이유는 평균을 double로 처리해야 하고, double보다 크면 -1, 작으면 -1, 같으면 아무런 행동도 하지 않는다 입니다.