[백준 17822] 원판 돌리기

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

17822번: 원판 돌리기

// 2시간 30분 // 1128kb	0ms
#include <cstdio>
int N, M, T;
int pann[50 + 3][50 + 3];	// 원판 최대 50개, 최대 수 50개까지 
bool trans[50 + 3][50 + 3];	// 인접한 수 바꿀지 말지 결정 


void input()
{
	scanf("%d %d %d", &N, &M, &T);
	for (int i = 1; i <= N; i++) {	// 몇개의 원판 
		for (int j = 1; j <= M; j++) {	// 몇개의 숫자 
			scanf("%d", &pann[i][j]);
		}
	}
}


void rotate_it(int x, int d, int k)
{
	switch (d)	// 어떤 방향으로 회전할 것인지 
	{
	case 0:					// 시계방향으로 
		while (k) {			// k번 회전한다
			int tmp = pann[x][M];
			for (int j = M; j >= 1; j--) {
				pann[x][j] = pann[x][j - 1];
			}
			pann[x][1] = tmp;
			k--;
		}
		break;
	case 1:					// 반시계방향으로 
		while (k) {			// k번 회전한다
			int tmp = pann[x][1];
			for (int j = 1; j < M; j++) {
				pann[x][j] = pann[x][j + 1];
			}
			pann[x][M] = tmp;
			k--;
		}
		break;

	}
}



void init()
{
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			trans[i][j] = false;
		}
	}
}


void erase_it()
{
	bool flag = false;
	int sum = 0;
	int num = 0;
	//printf("flag");
	//printf("%d\n", flag);
	//debug1();
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			sum += pann[i][j];
			if (pann[i][j]) num++;

			if (trans[i][j] == true) {
				pann[i][j] = 0;
				flag = true;
			}
		}
	}
	if (num == 0) return;	// 원판에 남아있는 숫자가 없는 경우 못지운다 

	if (flag == false) {	// 판을 다 돌았는데 바꿀 숫자가 없는 경우에는 
		double avg = (double)sum / num;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (pann[i][j] == 0) continue;
				if ((double)pann[i][j] > avg) pann[i][j] -= 1;
				else if ((double)pann[i][j] < avg) pann[i][j] += 1;
				//printf("[avg]%d %d\n", avg, pann[i][j]);
			}
		}
	}
}



void do_it(int x, int d, int k)	// 몇번째 원판, 방향, 몇번 회전 
{
	// 회전
	int new_x = x;
	while (new_x <= N) {
		rotate_it(new_x, d, k);
		new_x += x;
	}
	//printf("rotate");
	//debug();


	// 원판에 수가 남아있으면, 인접하면서 수가 같은 것을 모두 찾는다. 
	init();
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (pann[i][j] == 0) continue;
			int tmp = pann[i][j];
			if (i == 1 && tmp == pann[2][j]) {			// 첫번째 원판일 때 
				trans[1][j] = true;
				trans[2][j] = true;
			}
			if (i == N && tmp == pann[N - 1][j]) {		// 마지막 원판일 때 
				trans[i][j] = true;
				trans[N - 1][j] = true;
			}
			
			if (j == 1) {	// 첫번째 수 일 때 
				if (tmp == pann[i][2]) {
					trans[i][1] = true;
					trans[i][2] = true;
				}
				if (tmp == pann[i][M]) {
					trans[i][1] = true;
					trans[i][M] = true;
				}
			}
			if (j == M) {	// 마지막 수 일 때 
				if (tmp == pann[i][M - 1]) {
					trans[i][M] = true;
					trans[i][M - 1] = true;
				}
				if (tmp == pann[i][1]) {
					trans[i][1] = true;
					trans[i][M] = true;
				}
			}
			// 모든 원판 공통 확인 사항 
			if (tmp == pann[i][j - 1]) {
				trans[i][j] = true;
				trans[i][j - 1] = true;
			}
			if (tmp == pann[i][j + 1]) {
				trans[i][j] = true;
				trans[i][j + 1] = true;
			}
			if (tmp == pann[i - 1][j]) {
				trans[i][j] = true;
				trans[i - 1][j] = true;
			}
			if (tmp == pann[i + 1][j]) {
				trans[i][j] = true;
				trans[i + 1][j] = true;
			}
		}
	}
	erase_it();
	//printf("erase");
	//debug();
}



void simul()
{
	for (int t = 0; t < T; t++) {
		int x = 0, d = 0, k = 0;
		scanf("%d %d %d", &x, &d, &k);
		do_it(x, d, k);
	}
}


int output()
{
	int total = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			total += pann[i][j];
		}
	}
	return total;
}


int main()
{
	input();
	simul();
	int ans = output();
	printf("%d\n", ans);
	return 0;
}

C++이지만 사실 아무 라이브러리 없이 C로 짠 개빡구현 코드 ..... ㅋㅋㅋㅋㅋ 

이거 풀면서 삼성 기출 중에 "톱니바퀴" 문제가 많이 생각났다... 그것도 진짜 빡구현 했었는데.. ㅋㅋ쿠ㅜ 

언제쯤 나는 지성인처럼 코드를 짤 수 있을까 ... 뭐 그래도 암튼 돌아가기만 하면 되는거잖아요 ^^? ㅎ

 

 

// do_it( ) 함수

처음 Wrong answer를 받은 이유는 원판이 4개만 들어온다고 생각했기 때문이다 ㅋㅋ.. 

어쩐지 들어가자마자 틀렸다고 해서 좀 당황했었다. 문제의 조건에서 N은 50까지 될 수 있다. 따라서 입력받은 원판번호 x가 N보다 같거나 작을 때 까지 x의 배수에 해당하는 원판을 돌려주어야 한다. 

이는 다음과 같이 구현할 수 있다. 

// 회전
int new_x = x;
while (new_x <= N) {
    rotate_it(new_x, d, k);
    new_x += x;
}

다음으로 회전하고 온 원판에 인접하면서 수가 같은 것을 모두 찾는다. 

이거는 솔직히 생각 많이 안하고 문제에서 준 조건들 다 if문으로 구현했다.. 이런건 문제가 하라는 대로 해야한다. 자의적으로 해석하면 멸망한다. ㅋㅋ... 

 

그리고 나는 해당 숫자를 지울지 말지를 판단하기 위해 boolean 타입의 trans 배열을 선언하여, 만약 인접한 수가 같은 수라면 trans 배열을 true로 바꿔주었다. 이렇게 바꾼 배열을 erase_it( ) 함수에서 한 번에 삭제해주었다. 

 

 

// erase_it( ) 함수

이때 boolean 타입의 플래그를 또 선언해준 이유는, 원판을 다 돌았는데 삭제할 숫자가 없는 경우를 판별해주기 위함이다. 

trans 배열을 돌면서 그 값이 1인 칸은 모두 삭제하고(pann[i][j] = 0), 플래그를 true로 만들어 삭제한 이력이 있음을 표시한다. 

플래그가 false일 때는 남아있는 숫자들을 대상으로 평균을 만들어야 하는데, 이때 타입 캐스팅 조심해야 한다. int / int 를 하면 아무리 avg 변수를 double로 선언했어도 소수점 자리수가 반영되지 않는다. 따라서 sum이나 num 중 하나를 실수로 타입 캐스팅 해주고 연산을 진행해야 한다. 

만약 pann[i][j] == 0 이면 스루하고 평균보다 원판의 수가 클 때는 원판의 수에서 -1, 평균보다 원판의 수가 작을 때는 원판의 수에서 +1을 해준다. 

 

실수로 타입캐스팅 안하고 싶다면 다음과 같이 코드를 구현할 수 있다. 

if (pann[i][j] * num > sum) pann[i][j] -= 1;			
else if (pann[i][j] * num < sum) pann[i][j] += 1;

원판의 숫자와 num을 곱하여 그 값이 sum보다 크면, 해당 숫자는 당연히 평균값보다 크다. 

이 방법이 타입캐스팅 실수를 하지 않고 더 안전하게 구현할 수 있는 방법인 것 같다. 

---

++ 22.10.25 다시 풀었음 

범위 실수 진짜 죽을래.. ㅂㄷㅂㄷ 이렇게 행과 열이 다르게 주어지는 문제(대부분 그렇지만..) 는 R, C로 받는 것이 나을 것 같다.. 

N, M으로 두 번 실수하고 나서야 통과됨.. 

진짜 슬프다 이런거 진짜 실수하지 말아야지.. 

덱큐로 풀어보겠다고 삽질하지만 않았어도 한시간 컨 했는데...ㄲㅂ... 

근데 이런 자잘한 구현 문제는 시간초과 나지 않는 이상 그냥 배열로 구현할 것같다. 컨테이너 쓰면 iterator랑 range 때문에 생각해줄 것이 너무 많기 때문이다... 

전체적인 코드는 이전이랑 슷비.. 

#include <cstdio>
#include <deque>
int T;
int N, M;

int Pann[50 + 2][50 + 2];
int A[50 + 2][50 + 2];


void debug()
{
	printf("====================================\n");
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			printf("%d", Pann[i][j]);
		}
		printf("\n");
	}
}


void input()
{
	scanf("%d %d %d", &N, &M, &T);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf("%d", &Pann[i][j]);
		}
	}
}


void rotate_pann(int x, int d, int k)
{
	int num = -1;
	switch (d)
	{
	case 0:	// 시계방향
		for (int i = 0; i < k; i++) {
			num = Pann[x][M];
			for (int j = M; j >= 2; j--) {
				Pann[x][j] = Pann[x][j - 1];
			}
			Pann[x][1] = num;
		}
		break;
	case 1:	// 반시계방향
		for (int i = 0; i < k; i++) {
			num = Pann[x][1];
			for (int j = 1; j <= M - 1; j++) {
				Pann[x][j] = Pann[x][j + 1];
			}
			Pann[x][M] = num;
		}
		break;
	}
	//debug();
}



int erase_pann()
{
	std::fill(&A[0][0], &A[0][0] + sizeof(A) / sizeof(int), 0);
	
	for (int i = 1; i <= N; i++) {
		if (Pann[i][1] != 0 && Pann[i][2] != 0 && 
			Pann[i][1] == Pann[i][2]) A[i][1] = A[i][2] = -1;
		if (Pann[i][1] != 0 && Pann[i][M] != 0 && 
			Pann[i][1] == Pann[i][M]) A[i][1] = A[i][M] = -1;

		if (Pann[i][M] != 0 && Pann[i][M - 1] != 0 && 
			Pann[i][M] == Pann[i][M - 1]) A[i][M] = A[i][M - 1] = -1;
		if (Pann[i][M] != 0 && Pann[i][1] != 0 && 
			Pann[i][M] == Pann[i][1]) A[i][M] = A[i][1] = -1;

		for (int j = 2; j < M; j++) {
			if (Pann[i][j] != 0 && Pann[i][j - 1] != 0 && 
				Pann[i][j] == Pann[i][j - 1]) A[i][j] = A[i][j - 1] = -1;
			if (Pann[i][j] != 0 && Pann[i][j + 1] != 0 && 
				Pann[i][j] == Pann[i][j + 1]) A[i][j] = A[i][j + 1] = -1;
		}
		for (int j = 1; j <= M; j++) {
			if (Pann[1][j] != 0 && Pann[2][j] != 0 && 
				Pann[1][j] == Pann[2][j]) A[1][j] = A[2][j] = -1;
			if (Pann[N][j] != 0 && Pann[N - 1][j] != 0 && 
				Pann[N][j] == Pann[N - 1][j]) A[N][j] = A[N - 1][j] = -1;
		}
	}
	for (int i = 2; i < N; i++) {
		for (int j = 1; j <= M; j++) {
			if (Pann[i][j] != 0 && Pann[i - 1][j] != 0 && 
				Pann[i][j] == Pann[i - 1][j]) A[i][j] = A[i - 1][j] = -1;
			if (Pann[i][j] != 0 && Pann[i + 1][j] != 0 && 
				Pann[i][j] == Pann[i + 1][j]) A[i][j] = A[i + 1][j] = -1;
		}
	}

	int E = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (A[i][j] == -1) {
				E++;
				Pann[i][j] = 0;
			}
		}
	}
	//debug();
	return E;
}

void cal()
{
	int total = 0;
	int cnt = 0;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (Pann[i][j] != 0) {
				cnt++;
				total += Pann[i][j];
			}
		}
	}


	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (Pann[i][j] == 0) continue;
			if (Pann[i][j] * cnt > total) Pann[i][j] -= 1;
			else if (Pann[i][j] * cnt < total)	Pann[i][j] += 1;
		}
	}
	//debug();
}



int get_sum()
{
	int sum = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (Pann[i][j] == 0) continue;
			sum += Pann[i][j];
		}
	}
	return sum;
}



int choice_pann(int x, int d, int k)
{
	for (int i = 1; i <= N; i++) {
		if (x * i > N) break;
		rotate_pann(x * i, d, k);
	}
	int E = erase_pann();
	if (E == 0) cal();
	return get_sum();
}



int simul()
{
	int sum = 0;
	for (int t = 0; t < T; t++) {
		int x = 0, d = 0, k = 0;
		scanf("%d %d %d", &x, &d, &k);
		sum = choice_pann(x, d, k);		// 원판에 적힌 수의 합 
	}
	return sum;
}



int main()
{
	input();
	int ans = simul();
	printf("%d\n", ans);
	return 0;
}