백준 17822 - 원판 돌리기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/17822

17822번: 원판 돌리기

삼성 SW 역량테스트 문제입니다.

구현이 까다로웠지만, 출력 예시를 보면서 문제를 풀면 되는 문제였습니다.

 

문제 조건

출력 예시

문제를 풀기 위해서는 몇가지 구현을 해야합니다.

1. 원판 돌리기

2. 원판에서 겹치는 수 없애기

3. 겹치는 수가 없을 경우 평균을 구한뒤 원판을 바꾸기

 

 

1. 원판 돌리기

X는 돌릴 원판을 결정하는 수, D는 방향(시계 or 반시계), K는 돌릴 횟수,  M은 원판 위 숫자의 갯수 입니다

 

원판을 돌리는 경우는 i번째 원판이 (i % X == 0) 일 경우에만 해당 원판이 돌아갑니다.

해당 경우를 만족하는 원판일 경우 D와 K값에 따라서 원판을 돌립니다.

 

먼저 반시계 방향으로 돌릴때부터 생각하겠습니다.

(1 , 2 , 3 , 4 , 5 , 6) 으로 구성된 원판을 반시계 방향으로 한번 돌리면 (2 , 3 , 4 , 5 , 6 , 1) 이 됩니다.

반시계 방향으로 2번 돌릴 경우 (3 , 4 , 5 , 6 , 1 , 2) ,  3번 돌릴 경우 (4 , 5 , 6 , 1 , 2 , 3) 이 됩니다.

여기서 첫번째 칸의 값이 1에서 (1 + 돌린 횟수) 의 값으로 바뀐 것을 볼 수 있습니다.

다른 칸도 마찬가지이기에 i번 칸의 값은 (X + 돌린 횟수)로 바뀐 것을 볼 수 있습니다.

그렇다면 7번을 돌리면 (2 , 3 , 4 , 5 , 6 , 1)의 값이 됩니다.

i + 7 의 값과 i + 1의 값이 서로 같음을 알 수 있습니다.

여기서 유추할수 있는 것은 (i + K) % M 의 값으로 바뀜을 알 수 있습니다.

(i + K) % M의 값이 0이 되는 곳은 값이 M인 것을 보아 해당 칸의 값을 M으로 바꾸어주면 됩니다.

이를 배열에 적용하면 반시계 방향으로 돌릴 때의 변화값이 됩니다.

 

이번에는 시계 방향으로 돌릴 때를 생각해보겠습니다.

(1 , 2 , 3 , 4 , 5 , 6) 을 시계 방향으로 1번 돌리면 (6 , 1 , 2 , 3 , 4 , 5) 가 됩니다.

반시계 방향과 마찬가지로 같은 과정을 해보면 시계 방향일 때는 i번째 칸의 값은 i - K번쨰 칸의 값이 됨을 알 수 있습니다. 이때 i - K의 값이 0이하가 된다면 M을 더해주면 됩니다.

 

해당 과정은 Spin() 함수에 있으니 참고해주세요

 

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 

2. 원판에서 겹치는 수 없애기

(X , Y) 칸을 기준으로 상하좌우 칸 중, (X , Y)칸의 값과 겹치는 칸이 있으면 해당 칸을 빈칸으로 만들어줘야합니다.

저는 Flag라는 변수를 통해서 값이 겹치는 칸이 있는지의 여부를 확인했습니다.

겹치는 칸이 있을 경우 해당 칸의 값을 0으로 만들었는데, 다른 칸에서 값이 0인 칸끼리 서로 겹친다고 하면 안됨으로 항상 비교하는 칸의 값이 0보다 클때만 확인했습니다.

 

또한 순차적으로 원판을 없애는 것이 아닌 한번에 겹치는 수를 모두 없애는 것임으로 copy_map에 값을 저장했다가 확인이 끝난뒤에 map에 옮겨줬습니다.

 

해당 과정은 remain_same() 함수에 있으니 참고해주세요

 

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 

3. 겹치는 수가 없을 경우 평균을 구한 뒤 원판 바꾸기

겹치는 수를 없애는 과정에서 can_remain 변수를 만들어 겹치는 수를 없앨 경우 +1를 해줬습니다.

따라서 해당 변수의 값이 0이라면 겹치는 수가 없다는 의미임으로 평균을 구하는 과정을 해줬습니다.

 

map[x][y]의 값이 0보다 클때, sum 변수에 해당 값을 더해주면서 number 변수를 하나씩 증가했습니다.

마지막에 sum 변수의 값을 number 변수의 값으로 나누어주면 됩니다.

이때 주의할 점은 평균을 정수로 구하는 것이 아닌 소수점까지 모두 구해야합니다.

 

평균의 값보다 작은 수와 큰 수는 각각 +1, -1를 했습니다.

 

해당 과정은 sum_circle 함수에 있으니 참고해주세요

 

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 

 

문제 접근 과정

1. 조건에 따라 원판을 돌리기

2. 돌린 원판을 기준으로 겹치는 값이 있는지 확인하고 값 없애기

3. 겹치는 값이 없을 경우 평균을 구해서 원판의 값을 바꾸기

4. 1 ~ 3 과정을 T번 반복하기

5. 과정이 모두 끝난 후 원판에 남은 수의 합 구하기

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>

using namespace std;

int circle[51][51]; // 각각 0칸은 안쓰는 칸
int copy_circle[51][51];
int N, M, T;
int can_remain;
typedef struct turn {
	int x;
	int d; // 0 -> 시계방향 / 1 -> 반시계방향
	int k;
}turn;
turn Turn[51];

void Spin(int way, int num, int x) {
	if (way == 1) {
		int new_circle[51] = { 0, };
		for (int i = 1; i <= M; i++) {
			int xx = (i + num) % M;
			if (xx == 0) xx = M;
			new_circle[i] = circle[x][xx];
		}
		for (int i = 1; i <= M; i++) {
			circle[x][i] = new_circle[i];
		}
	}
	else {
		int new_circle[51] = { 0, };
		for (int i = 1; i <= M; i++) {
			int xx = i - num;
			if (xx <= 0) xx += M;
			new_circle[i] = circle[x][xx];
		}
		for (int i = 1; i <= M; i++) {
			circle[x][i] = new_circle[i];
		}
	}
}

void sum_circle() {
	int sum = 0, number = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (circle[i][j] > 0) {
				sum += circle[i][j];
				number++;
			}
		}
	}
	double aver = (double)sum / (double)number;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (circle[i][j] > 0) {
				if ((double)circle[i][j] > aver) circle[i][j] -= 1;
				else if((double)circle[i][j] < aver) circle[i][j] += 1;
			}
		}
	}
}

void remain_same(int x, int y) {
	bool flag = false;
	int X = circle[x][y];
	int x1 = x - 1;
	int x2 = x + 1;
	int y1 = y - 1;
	int y2 = (y + 1) % M;
	if (y1 <= 0) y1 += M;
	if (y2 == 0) y2 = M;
	if (circle[x][y1] == X && X != 0) {
		copy_circle[x][y1] = 0;
		flag = true;
	}
	if (circle[x][y2] == X && X != 0) {
		copy_circle[x][y2] = 0;
		flag = true;
	}
	if (x1 >= 1 && circle[x1][y] == X && X !=0) {
		copy_circle[x1][y] = 0;
		flag = true;
	}
	if (x2 <= M && circle[x2][y] == X && X != 0) {
		copy_circle[x2][y] = 0;
		flag = true;
	}
	if (flag) {
		copy_circle[x][y] = 0;
		can_remain++;
	}
}

void copy_map(int x) {
	if (x == 0) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				copy_circle[i][j] = circle[i][j];
			}
		}
	}
	else {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				circle[i][j] = copy_circle[i][j];
			}
		}
	}
}

void turn_circle(int x) {
	for (int i = 1; i <= N; i++) {
		if (i % Turn[x].x == 0) {
			Spin(Turn[x].d, Turn[x].k, i);
		}
	}
	copy_map(0);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			remain_same(i, j);
		}
	}
	if (can_remain == 0) sum_circle();
	else copy_map(1);
	can_remain = 0;
}

void solve() {
	for (int i = 1; i <= T; i++) {
		turn_circle(i);
	}
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			ans += circle[i][j];
		}
	}
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> T;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> circle[i][j];
		}
	}
	for (int i = 1; i <= T; i++) {
		cin >> Turn[i].x >> Turn[i].d >> Turn[i].k;
	}
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글 남겨주세요