(c++)백준 17822번: 원판 돌리기

www.acmicpc.net/problem/17822

17822번: 원판 돌리기

[풀이]

구현해야할 것

1. 원판

2. 원판 돌리기

3. 인접하면서 같은 수 찾기

4. 원판에 적힌 수의 평균 찾고 평균보다 큰 수에서 1 빼고 작은수에 1 더하기

 

1. 원판은 2차원 배열 int Circle[][]로 구현하였다. Circle[i][j]는 i번 원판의 j번째 숫자를 의미한다.

2. 돌릴 원판의 번호와 방향과 돌릴 칸 수를 인수로 보내 시계방향 또는 반시계방향으로 해당 원판을 돌리도록 하였다. 

3. 같은 원판 내에서 인접하면서 같은 수를 찾고, 다른 원판들 사이에서 인접하면서 같은 수를 찾았다.

*인접하면서 같은 수는 bool check[][]에 true로 체크해놓고 같은 원판, 다른 원판 모두 살핀 다음 true로 체크된 자리의 숫자를 0으로 바꿔주었다.

4. 원판에서 0이 아닌 숫자들의 개수와 합을 구하고 합/개수 연산으로 평균을 구하였다.

*평균을 double로 구하지 않으면 답이 틀리게 된다. 문제에 소수점 아래를 버린다고 써있지 않긴 하다.

 

#include <iostream>
#include <vector>
using namespace std;

int N, M, T;
int Circle[51][51];//원판 숫자 저장

//n번 원판 d방향으로 k칸 회전
void TurnCircle(int n, int d, int k) {
	//시계방향
	if (d == 0) {
		//k칸 회전
		while (k--) {
			int tmp = Circle[n][1];
			Circle[n][1] = Circle[n][M];
			for (int i = M - 1; i > 1; i--) {
				Circle[n][i + 1] = Circle[n][i];
			}
			Circle[n][2] = tmp;
		}
	}
	//반시계방향
	else if (d == 1) {
		//k칸 회전
		while (k--) {
			int tmp = Circle[n][M];
			Circle[n][M] = Circle[n][1];
			for (int i = 2; i < M; i++) {
				Circle[n][i - 1] = Circle[n][i];
			}
			Circle[n][M - 1] = tmp;
		}
	}
}

//원판에 수가 남아있는지 확인
bool findNum() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (Circle[i][j] != 0)
				return true;
		}
	}
	return false;
}

bool findSame() {
	bool res = false;
	//없어질 숫자들 표시
	bool check[51][51] = { false, };
	//같은 원판에서
	for (int c = 1; c <= N; c++) {
		for (int n = 1; n <= M; n++) {
			if (Circle[c][n] == 0)
				continue;
			//1번 숫자일 때
			if (n == 1) {
				if (Circle[c][n] == Circle[c][M]) {
					check[c][n] = true;
					check[c][M] = true;
				}
				if (Circle[c][n] == Circle[c][n + 1]) {
					check[c][n] = true;
					check[c][n + 1] = true;
				}
			}
			//M번 숫자일 때
			if (n == M) {
				if (Circle[c][n] == Circle[c][n - 1]) {
					check[c][n] = true;
					check[c][n - 1] = true;
				}
				if (Circle[c][n] == Circle[c][1]) {
					check[c][n] = true;
					check[c][1] = true;
				}
			}
			else {
				if (Circle[c][n] == Circle[c][n - 1]) {
					check[c][n] = true;
					check[c][n - 1] = true;
				}
				if (Circle[c][n] == Circle[c][n + 1]) {
					check[c][n] = true;
					check[c][n + 1] = true;
				}
			}
		}
	}
	//다른 원판에서
	for (int n = 1; n <= M; n++) {
		for (int c = 1; c < N; c++) {
			if (Circle[c][n] == 0)
				continue;
			if (Circle[c][n] == Circle[c + 1][n]) {
				check[c][n] = true;
				check[c + 1][n] = true;
			}
		}
	}
	for (int c = 1; c <= N; c++) {
		for (int n = 1; n <= M; n++) {
			if (check[c][n] == true) {
				Circle[c][n] = 0;
				res = true;
			}
		}
	}
	return res;
}

void doElse() {
	int ncnt = 0;//원판에 적힌 수의 개수
	int nsum = 0;//원판에 적힌 수의 총합
	//평균 구하기
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (Circle[i][j] != 0) {
				ncnt++;
				nsum += Circle[i][j];
			}
		}
	}
	double m = (double)nsum / (double)ncnt;//평균(소수점 아래 버리라는 말이 없음)
	//평균보다 큰 수에서 1을 빼고 작은 수에 1을 더하기
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (Circle[i][j] != 0) {
				if (Circle[i][j] > m) {
					Circle[i][j]--;
				}
				else if (Circle[i][j] < m) {
					Circle[i][j]++;
				}
			}
		}
	}
}

int getSum() {
	int res = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			res += Circle[i][j];
		}
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin >> N >> M >> T;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> Circle[i][j];
		}
	}
	int x, d, k;
	for (int i = 1; i <= T; i++) {
		//cin >> turn[i].x >> turn[i].d >> turn[i].k;
		cin >> x >> d >> k;
		//번호가 x의 배수인 원판 돌리기
		for (int n = x; n <= N; n += x) {
			TurnCircle(n, d, k);
		}
		//원판에 수가 없으면
		if (findNum() == false) {
			cout << 0 << '\n';
			return 0;
		}
		//인접하면서 수가 같은 것 찾기
		if (findSame() == false) {//없으면
			doElse();
		}
	}
	cout << getSum() << '\n';
	return 0;
}

+set STL 사용한 풀이

#include <iostream>
#include <set>
using namespace std;

struct Pos{
	int n;
	int m;
};

int N, M, T;
int Circle[51][51];//둘 다 1부터 시작
set<pair<int,int>>Same;//인접하면서 수가 같은 것 찾아서 저장

//원판 돌리기
void Turn(int x,int d,int k) {
	//번호가 x의 배수인 원판
	for (int n = x; n <= N; n += x) {
		//시계방향
		if (d == 0) {
			//k칸 회전
			for (int t = 0; t < k; t++) {
				int tmp = Circle[n][M];
				for (int i = M - 1; i >= 1; i--) {
					Circle[n][i + 1] = Circle[n][i];
				}
				Circle[n][1] = tmp;
			}
		}
		//반시계방향
		else if (d == 1) {
			//k칸 회전
			for (int t = 0; t < k; t++) {
				int tmp = Circle[n][1];
				for (int i = 2; i <= M; i++) {
					Circle[n][i - 1] = Circle[n][i];
				}
				Circle[n][M] = tmp;
			}
		}
	}
}

int Sum() {
	int res = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			res += Circle[i][j];
		}
	}
	return res;
}

bool findNum() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (Circle[i][j] > 0)
				return true;
		}
	}
	return false;
}

void findSame() {
	bool check[51][51] = { false, };
	//각각 원판에서 같은 것 찾기
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (Circle[i][j] == 0)
				continue;
			if (j == 1) {
				if (Circle[i][j] == Circle[i][j + 1]) {
					Same.insert(make_pair(i, j));
					Same.insert(make_pair(i, j + 1));
				}
				if (Circle[i][j] == Circle[i][M]) {
					Same.insert(make_pair(i, j));
					Same.insert(make_pair(i, M));
				}
			}
			else if (j == M) {
				if (Circle[i][j] == Circle[i][1]) {
					Same.insert(make_pair(i, j));
					Same.insert(make_pair(i, 1));
				}
				if (Circle[i][j] == Circle[i][j - 1]) {
					Same.insert(make_pair(i, j));
					Same.insert(make_pair(i, j - 1));
				}
			}
			else {
				if (Circle[i][j] == Circle[i][j + 1]) {
					Same.insert(make_pair(i, j));
					Same.insert(make_pair(i, j + 1));
				}
				if (Circle[i][j] == Circle[i][j - 1]) {
					Same.insert(make_pair(i, j));
					Same.insert(make_pair(i, j - 1));
				}
			}
		}
	}
	//다른 원판에서 같은 것 찾기
	for (int j = 1; j <= M; j++) {
		for (int i = 1; i < N; i++) {
			if (Circle[i][j] == 0)
				continue;
			if (Circle[i][j] == Circle[i + 1][j]) {
				Same.insert(make_pair(i, j));
				Same.insert(make_pair(i + 1, j));
			}
		}
	}
	bool res = false;
	
	//인접하면서 수가 같은 것이 있으면
	if (!Same.empty()) {
		res = true;
		for (auto num : Same) {
			Circle[num.first][num.second] = 0;
		}
	}
	//없으면
	if(res==false) {
		int cnt = 0;
		int nsum = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (Circle[i][j] != 0) {
					cnt++;
					nsum += Circle[i][j];
				}
			}
		}
		double Ave = (double)nsum / (double)cnt;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (Circle[i][j] == 0)
					continue;
				if (Circle[i][j] < Ave)
					Circle[i][j]++;
				else if (Circle[i][j] > Ave)
					Circle[i][j]--;
			}
		}
	}
	Same.clear();
}

int main() {
	cin >> N >> M >> T;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> Circle[i][j];
		}
	}
	int x, d, k;
	while (T--) {
		cin >> x >> d >> k;
		Turn(x, d, k);
		//원판에 수가 없으면
		if (findNum() == false) {
			cout << 0 << '\n';
			return 0;
		}
		findSame();
	}
	cout << Sum() << '\n';
	return 0;
}