[BOJ]백준 17822번: 원판 돌리기

 

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

17822번: 원판 돌리기

이것도 역량테스트 기출인 단순 구현문제다

원판돌리기를 비롯한 많은 회전 문제들은 실제로 회전하지 않아도 인덱스를 활용하면 아주 깔끔하게 문제를 풀 수 있다

 

원판

위와 같은 원판이 있을 때, 아래는 원판을 회전시키는 예시이다.

원판의 번호는 안쪽부터 1,2,3,... 으로 증가한다. 회전한 뒤 인접하면서 수가 같은 쌍을 모두 찾고,

1. 원판에서 인접하면서 같은 수를 모두 지운다

2. 없는 경우에는 원판에 적힌 수의 평균을 구해서 평균보다 큰 수에는 1을 빼고, 작은 수에는 1을 더한다.

이 과정을 T번해서, 원판에 적힌 수의 총 합을 구하면 된다.

 

내가 사용한 자료구조

int n, m, t, x, d, k          //사용자에게 입력받는 변수

int p[51][51]                //원판의 숫자를 저장할 배열

int idx[51]                   //각 번호의 원판의 시작점을 저장하는 인덱스 배열(이것으로 회전 표현 가능)
bool chk[51][51]           //회전이 끝난 뒤 인접하면서 수가 같은 것을 체크할 배열

 

회전할 때는 해당 번호의 idx[]배열 값을 바꿔줬고, 인접하면서 수가 같은 것을 체크할 때는 각 원판마다 m개의 번호를 체크하되, 해당 원판과 다른 원판의 인덱스 값을 각각 더해줬다.

말로 설명하면 조금 복잡해서, 소스코드를 첨부한다 ^.^

 

#include <cstdio>
#include <cstring>
using namespace std;
int n, m, t, x, d, k, p[51][51], idx[51], ans;
bool chk[51][51];
int main() {
	scanf("%d%d%d", &n, &m, &t);
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < m; j++)scanf("%d", &p[i][j%m]);
	while (t--) {
		bool b = false;
		int sum = 0, cnt = 0;
		double avg;
		scanf("%d%d%d", &x, &d, &k);
		for (int i = x; i <= n; i += x) idx[i] = d ? (idx[i] + k) % m : (idx[i] - k + m) % m;

		for (int i = 1; i <= n; i++)
			for (int j = idx[i]; j < idx[i] + m; j++) 
			if(p[i][j%m]){
				if (p[i][j%m] == p[i][(j + 1) % m]) {
					chk[i][j%m] = chk[i][(j + 1) % m] = 1;
					b = true;
				}
				if (i != n && p[i][j%m] == p[i + 1][(j - idx[i] + idx[i+1])%m]) {
					chk[i][j%m] = chk[i + 1][(j - idx[i] + idx[i+1])%m] = 1;
					b = true;
				}
			}
		if (b) {
			for (int i = 1; i <= n; i++)
				for (int j = 0; j < m; j++)
					if (chk[i][j%m])p[i][j%m] = 0;
		}
		else {
			for (int i = 1; i <= n; i++)
				for (int j = 0; j < m; j++)
					if (p[i][j%m]) {
						sum += p[i][j%m];
						cnt++;
					}

			avg = (double)sum / cnt;
			for (int i = 1; i <= n; i++)
				for (int j = 0; j < m; j++) {
					if (p[i][j%m] > avg) p[i][j%m]--;
					else if (p[i][j%m] && p[i][j%m] < avg) p[i][j%m]++;
				}
		}
		memset(chk, false, sizeof(chk));
	}
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < m; j++)ans += p[i][j%m];
	printf("%d", ans);
	return 0;
}