백준 17822번 원판 돌리기 문제 풀이

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

17822번: 원판 돌리기

문제 개요

백준저지 17822번 문제 원판 돌리기 문제 풀이입니다.

 

규칙에 따라 원판을 돌리고, 인접 수를 지우고, 수를 변경하고 하는 식의 문제입니다.

 

하라는대로 하면 되는 시뮬레이션 문제에 해당합니다.

 

N, M, T값이 50으로 작은편이므로, 원판을 죄다 돌려버리고 돌릴때 마다 다 체크를 한다고 해봅시다.

 

1번 돌릴때 마다 인접한 원판 수들을 체크를 해야하는데, 최대 원판에 쓰인 수의 개수는 N * M개 이므로 최대 50*50 = 2500개입니다.

 

2500개의 수를 50번 확인한다고 하면 125,000번으로 12만 5천번 정도됩니다.

 

그리고 그 때 마다 원판위의 숫자들을 shift한다고 하면, 모든 원판의 수를 다 shift하고 그 양이 50과 같이 큰 값이라 하면

 

50^4 = 6,250,000으로 625만번입니다. shift하는 것을 한번씩 여러번 반복하는 식으로 매우 대충 구현한다는 가정하에 대충 이정도 값이 나옵니다.

 

그런데 shift하는 것은 한번에 점프뛰는 방식으로도 가능하기 때문에 이정도까지도 안나옵니다.

 

고로 결론은, 그냥 그대로 따라하는 시뮬레이션 방식으로 구현해도 충분히 시간안에는 들어오는 크기의 N,M,T 값이라는 것입니다.

 

(대충 1억번 연산에 1초 정도 걸린다고 봅니다.)

 

구현 전략

원판 돌리는 연산을 간편하게 하기 위해서 bias라는 배열을 따로 두고, [원판][위치] 의 값을 읽거나 쓸 때에는 별도의 getter, setter 함수를 만들어서 코드를 작성해 보았습니다.

 

이녀석의 원리를 조금 설명드려 보자면 예를들어 다음과 같은 원판이 있다고 칩시다. 한 원판에 숫자가 4개 쓰여있으니 M=4가 됩니다.

12시 부터 시계방향으로 숫자를 읽는다면 1,2,3,4 가 되겠지요?

 

이 원판을 시계방향으로 90도 돌리면 다음과 같은 모양이 됩니다.

 

마찬가지로 12시 부터 읽는다면 4,1,2,3이 됩니다.

 

이를 잘라서 평평하게 핀다고 생각해봅시다.

 

그러면 초기의 1,2,3,4는 다음 모양과 같게 나옵니다.

그리고 시계방향으로 90도 돌린 4,1,2,3은 다음과 같게 나옵니다.

실제로 C언어 배열에는 위와 같이 연속된 메모리에 값이 저장이 되겠지요. 근데 그렇다면 한번 원판을 돌릴 때 마다 4개(M개)의 칸의 값을 모두 바꾸어 주어야 하는데, 발상을 조금 바꾸어봅시다.

 

값은 맨 처음 그대로 1,2,3,4로 저장을 하되, 읽는 순서만 바꾸는 거죠.

 

처음 1,2,3,4가 나오기 위해서는 인덱스 읽는 순서를 0,1,2,3으로 읽고, 시계방향으로 90도 돌린 경우는 인덱스를 3,0,1,2의 순서로 읽는것입니다.

그러면 아까처럼 값을 바꾸는 경우와 똑같은 값이 나오게 됩니다.

 

마찬가지로, 반시계방향으로 90도 돌린 경우는 인덱스를 1,2,3,0의 순서로 읽게 되겠지요?

 

따라서 원판이 시계방향으로 돌리게 되면 bias값에 -1을 해 줄것이고, 반시계 방향으로 돌리게 되면 bias값에 +1를 해줍니다.

 

시계방향으로 한번 돌리고 반시계 방향으로 한번 돌리면 결론적으로 원래 자리로 돌아오게 되는데 bias값에는 이러한 점도 적용이 되게 됩니다.

 

즉 bias값은 맨 처음 값을 몇 번째 인덱스부터 읽을 것인지를 나타내게 되는 것이지요.

 

하지만 bias값이 4보다 크거나 음수가 나타날 수 있으니, 이 bias값이 0이상 3이하(M-1)의 값만 나오게 하도록 모듈러(나머지)연산을 해 줍니다.

 

음수의 경우 모듈러 연산을 해도 음수가 나오기 때문에 4(M값)만큼을 더해서 0이상 3이하의 값이 나오게 되는 것입니다.

 

 

 

디버깅을 위해서 dump함수도 작성했는데, 활성화 하기 위해서는 dump 함수의 return 값을 제거하고 사용하시면 됩니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define DEL 99999
int num[55][55];
int bias[55];
int N, M, T;
typedef pair<int, int> pii;
void dump(const char[]);
int get_num(int i, int j) {
	//i번째 원판의 j번째 위치 녀석 값 가져오기
	j += bias[i];
	while (j < 0) {
		j += M;
	}
	j %= M;
	return num[i][j];
}
void set_num(int i, int j, int v) {
	//i번째 원판의 j번째 위치 녀석 값을 v로 셋팅
	j += bias[i];
	while (j < 0) {
		j += M;
	}
	j %= M;
	num[i][j] = v;
}
void process() {
	//인접수 날리고, 값 조정 한번에 하는 함수
	bool changed = false;
	vector<pii> del; //지울 수 좌표들 모음
	del.clear();

	//같은 원판 사이에 인접한 수들 찾아내기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int a = get_num(i, j);
			int b = get_num(i, j + 1);
			if (a != DEL && b != DEL && a == b) {
				del.push_back({ i,j });
				del.push_back({ i,j + 1 });
				changed = true;
			}
		}
	}
	//다른 원판 사이에 인접한 수들 찾아내기
	for (int i = 0; i + 1 < N; i++) {
		for (int j = 0; j < M; j++) {
			int a = get_num(i, j);
			int b = get_num(i + 1, j);
			if (a != DEL && b != DEL && a == b) {
				del.push_back({ i, j });
				del.push_back({ i + 1, j });
				changed = true;
			}
		}
	}

	//지울 녀석들 모아서 지우기
	for (auto p : del) {
		set_num(p.first, p.second, DEL);
	}
	dump("지운뒤");

	//지운 수가 없으면 계속 진행
	if (changed) return;

	int cnt, sum;
	cnt = sum = 0;
	//지워지지 않은 수와, 그 수들의 총합 을 구함
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (num[i][j] != DEL) {
				cnt++;
				sum += num[i][j];
			}
		}
	}

	//남은 수들이 평균보다 크면 -1, 작으면 +1 시킴.
	//나누기를 안쓰는 이유는 정수 소수점 잘리는 부분 때문
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (num[i][j] != DEL) {
				if (num[i][j] * cnt > sum) {
					num[i][j]--;
				}
				else if (num[i][j] * cnt < sum) {
					num[i][j]++;
				};
			}
		}
	}
	dump("덧뺄샘이후");
}
int main() {
	cin >> N >> M >> T;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> num[i][j];
		}
	}
	while (T--) {
		//회전 시킬 값들 받기
		int x, d, k;
		cin >> x >> d >> k;
		int v = x;
		int shift = k * (d == 0 ? -1 : +1);
		dump("돌리기전");
		while (v <= N) {
			//bias 배열에다가 값을 더하는식으로, 회전시킴
			bias[v-1] += shift;
			v += x;
		}
		dump("돌린뒤");
		//인접수 지우고 하는 처리들을 여기서 함
		process();
	}

	//남은 수 다 더해서 출력
	int ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (num[i][j] != DEL) {
				ans += num[i][j];
			}
		}
	}
	cout << ans << endl;

}
void dump(const char str[]) {
#ifndef WIN32
	return;
#endif
	puts(str);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cout << get_num(i, j) << ' ';
		}
		cout << endl;
	}
	cout << "============================" << endl;
}