[문제 링크]
https://www.acmicpc.net/problem/17822
17822번: 원판 돌리기
반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j
www.acmicpc.net
[문제 풀이]
전형적인 삼성의 시뮬레이션 문제이다.
처음에 원판에 있는 수들의 인접하는 조건이 나와있다.
[문제 조건1]
- (i, 1)은 (i, 2), (i, M)과 인접하다.
- (i, M)은 (i, M-1), (i, 1)과 인접하다.
- (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
- (1, j)는 (2, j)와 인접하다.
- (N, j)는 (N-1, j)와 인접하다.
- (i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)
복잡하게 설명되어 있는 것 같지만 그림으로 보면 이해가 쉽다.
문제 예시처럼 N=3, M=4인 경우를 살펴보겠다.
다음과 같은 원판이 있을 때 반지름이 1인 원판은 [1, 1, 2, 3]이다.
반지름이 1인 원판에서 첫 번째 1의 인접한 수는 같은 원판의 양 옆 숫자 1,3과 두 번째 원판의 같은 자리에 있는 5이다.
반지름이 2인 원판에서 5의 인접한 수는 같은 원판의 양 옆 숫자 2, 2와 첫 번째 원판과 세 번째 원판의 같은 자리에 있는 1, 3이다.
반지름이 3인 원판에서 1의 인접한 수는 같은 원판의 양 옆 숫자 3, 3과 두 번째 원판의 같은 자리에 있는 2이다.
이런 식으로 인접한 수의 조건을 만족하게 된다.
우리는 이 원판을 돌려야 한다. 원판은 시계방향으로 돌릴 수 있고, 반시계 방향으로 돌릴 수 있다.
첫 번째 원판을 시계방향으로 1번 회전시킨다면 [1, 1, 2 ,3] -> [3, 1, 1, 2]가 될 것이다. 여기서 시계방향으로 한 번 더 회전시킨다면 [3, 1, 1, 2] -> [2, 3, 1, 1]이 될 것이다.
두 번째 원판을 반시계 방향으로 1번 회전시킨다면 [5, 2, 4, 2] -> [2, 4, 2, 5]가 될 것이다.
[문제 조건2]
원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할 때 사용하는 변수는 xi, di, ki이다.
- 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
- 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
- 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
- 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.
원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.
문제 조건이 복잡해 보이면서도 간단해 보인다. 1번부터 차근차근 살펴보자.
1. 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
소스 코드의 move함수에 해당하는 내용이다.
처음에 Xi의 배수라는 조건을 봤을 때 "Xi가 1이면 전부 다 돌리는 건가?"라는 생각을 하고 문제 조건 1을 봤는데 Xi는 2이상이다. 이런 시뮬레이션 문제에서는 조건 하나하나를 자세히 봐야 한다고 생각한다. (그래야 삽질을 덜 하고 빠르게 풀 수 있다고 생각)
원판의 회전 방법은 미리 정해져 있기 때문에 T번을 반복하면서 Xi, Di, Ki 변수를 받아준다. 나는 x, d, K 변수를 사용했다.
예를 들어 2 0 1이라는 수를 입력했으면 2의 배수인 원판을 시계 방향으로 1번 회전시키라는 뜻이다.
x의 배수인 원판을 돌리라고 했으므로 원판의 번호가 x로 나누어 떨어질 때 돌리면 된다.
시계 방향일 때와 반시계 방향일 때로 나누어서 원판을 돌려준다.
시계 방향일 때는 원판의 m번째 숫자를 tmp에 저장한다. (i번째 원판이라면 MAP[i][m], m은 원판의 마지막 인덱스)
자신의 인덱스의 왼쪽에 있는 숫자를 현재 인덱스에 저장한다. 이것을 m번째 인덱스부터 2번째 인덱스까지 진행한다.
마지막으로 tmp에 저장했던 m번째 숫자를 1번째 인덱스에 저장하면 시계방향으로 1칸 회전한 효과를 얻을 수 있다.
반시계 방향일 때는 반대로 진행한다. 원판의 1번째 숫자를 tmp에 저장한다. (i번째 원판이라면 MAP[i][1], 인덱스는 1부터 시작)
자신의 인덱스의 오른쪽에 있는 숫자를 현재 인덱스에 저장한다. 이것을 1번째 인덱스부터 m-1 인덱스까지 진행한다.
마지막으로 tmp에 저장했던 1번째 숫자를 m번째 인덱스에 저장하면 반시계 방향으로 1칸 회전한 효과를 얻을 수 있다.
원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
- 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
- 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.
소스 코드의 remove 함수에 해당하는 내용이다.
본인은 이 구현을 위해 TEMP라는 2차원 배열을 사용했다. 처음에 TEMP배열을 사용하지 않아서 5번 예제의 답을 구할 수 없었다. TEMP배열을 사용한 이유는 뒤에서 설명하겠다.
또한, flag 변수를 통해 2번을 진행할 것인지 아닌지에 대해 정하였다. 모든 원판을 탐색하면서 1번의 경우가 한 번이라도 나온다면 2번을 진행하지 않고 한 번도 나오지 않았다면 2번을 진행하였다.
문제 조건 1을 보면 첫 번째 원판에서는 각 숫자의 인접한 수가 3개이다. 마지막 원판도 각 숫자의 인접한 수가 3개이다. 그 외에는 4개의 수가 인접한다. 이를 통해 조건문을 원판이 첫 번째일 때, 마지막일 때, 그 외일 때로 나누었다.
여기서 중요한 것은 1번 인덱스와 m번 인덱스가 인접한다는 것이다. 1번 인덱스와 m번 인덱스가 인접한다는 것을 어떻게 구현해야 할지 생각해봐야 한다.
본인은 2개의 idx 변수를 만들어서 현재 인덱스에서 -1 한 것과 +1 한 것을 저장하였다.
예를 들어 현재 인덱스가 2이면 idx1과 idx2에는 각각 1, 3을 저장한다.
만약 idx1이 0이 된다면 현재 인덱스가 1이라는 뜻이므로 idx1을 m으로 바꿔준다.
만약 idx2가 m+1이 된다면 현재 인덱스가 m이라는 뜻이므로 idx2를 1로 바꿔준다.
그리고 MAP의 현재 인덱스와 인접한 인덱스의 숫자가 같다면 해당 인덱스들의 숫자를 TEMP배열에서 0으로 바꿔준다.
여기서 숫자 0은 문제에서 x를 표현한다.
비교는 MAP에서 하고 실제로 바꿔주는 건 TEMP에서 하는 이유가 뭘까?
5번 예제를 생각해보자.
4 6 3
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8
4 5 6 7 8 9
2 1 4
3 0 1
2 1 2
여기서 첫 번째 회전을 보면 2의 배수인 원판을 반시계 방향으로 4칸 회전을 시킨다.
회전을 시키고 난 뒤 원판의 상태이다.
1 2 3 4 5 6
6 7 2 3 4 5
3 4 5 6 7 8
8 9 4 5 6 7
첫 번째 회전에서는 각각의 원판에서 같은 숫자의 인접한 수가 없기 때문에 평균을 구하고 평균보다 큰 수는 -1, 작은 수는 +1을 한다. 총합은 120이고 숫자가 24개이기 때문에 평균은 5가 된다. 5보다 큰 수는 +1, 작은 수는 -1을 하였다.
여기서 본인이 실수한 부분을 설명하자면 문제에서 평균보다 큰 수는 +1을 하라고 했고, 작은 수는 -1을 하라고 했다.
근데 예제를 보니 평균보다 큰 수는 -1을 했는데 같은 숫자도 +1을 했길래 당연히 같거나 작은 수를 +1을 해줬다.
하지만 문제를 대충 보면 안 되는 이유가 여기에 있다.
22/6은 3.6666667이다. 즉, 3.67보다 작은 수는 +1, 큰 수는 -1을 하라는 의미이다. 본인은 문제를 대충 읽고 22/6을 정수로 변환하여 계산을 해서 계속 틀렸다. 이런 실수는 주의해야 할 것 같다. (소스 코드의 solve() 함수)
다시 문제로 돌아와서 계산을 한 뒤 원판의 상태이다.
2 3 4 5 5 5
5 6 3 4 5 5
4 5 5 5 6 7
7 8 5 5 5 6
본인은 처음에 MAP 하나를 사용하여 현재 보고 있는 숫자에서 인접한 수가 같으면 0으로 바꿔주었다.
하지만 그럴 경우 제대로 결과가 나오지 않는다.
현재 이 원판의 상태에서 두 번째 회전(3의 배수인 원판을 시계방향으로 1칸 회전)을 정상적으로 진행하면 이런 결과가 나온다.
2 3 4 5 5 5 2 3 4 0 0 0
5 6 3 4 5 5 0 6 3 4 0 0
7 4 5 5 5 6 0 4 0 0 0 0
7 8 5 5 5 6 0 8 0 0 0 0
왼쪽은 회전을 한 상태이고, 오른쪽은 인접한 숫자가 같을 때 0으로 표시한 상태이다.
TEMP 배열을 이용하면 이렇게 정상적인 결과를 얻을 수 있지만 MAP 하나로 remove 함수를 사용하면 다른 결과를 얻게 된다.
2 3 4 5 5 5 2 3 4 0 0 0
5 6 3 4 5 5 5 6 3 4 0 0
7 4 5 5 5 6 0 4 0 0 0 0
7 8 5 5 5 6 0 8 0 0 5 0
이렇게 다른 결과를 얻을 수 있기 때문에 TEMP 배열을 하나 더 선언하여 MAP에서 인접한 수가 같다면 TEMP 배열에서 0으로 바꿔주었다. 그러면 정상적인 결과를 얻을 수 있다.
또한, remove 함수를 진행할 때 TEMP배열이 0이라면 건너뛰었다. 그 이유는 건너뛰지 않아도 값에는 변화가 없지만 x와 x(숫자로는 0과 0)가 인접한 것은 문제 조건과 맞지 않기 때문이다.
이런 방식으로 T번 회전을 모두 마친 뒤에 남아 있는 원판의 수를 모두 더하면 된다.
[소스 코드]
#include <bits/stdc++.h>
using namespace std;
int n, m, t, x, d, K;
int MAP[51][51];
int TEMP[51][51];
int ans;
void setting() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
TEMP[i][j] = MAP[i][j];
}
}
}
void setting1() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
MAP[i][j] = TEMP[i][j];
}
}
}
void move(int x, int d, int K) {
cin >> x >> d >> K;
for (int i = 1; i <= n; i++) {
if (i % x == 0) {
if (d == 0) {
for (int j = 0; j < K; j++) {
int tmp = MAP[i][m];
for (int k = m; k >= 2; k--) {
MAP[i][k] = MAP[i][k - 1];
}
MAP[i][1] = tmp;
}
}
else if (d == 1) {
for (int j = 0; j < K; j++) {
int tmp = MAP[i][1];
for (int k = 1; k <= m - 1; k++) {
MAP[i][k] = MAP[i][k + 1];
}
MAP[i][m] = tmp;
}
}
}
}
}
bool remove() {
bool flag = false;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (TEMP[i][j] == 0) continue;
if (i == 1) {
int idx1 = j - 1;
int idx2 = j + 1;
if (idx1 == 0) idx1 = m;
if (idx2 == m + 1) idx2 = 1;
if (MAP[i][j] == MAP[i][idx1]) {
TEMP[i][j] = 0;
TEMP[i][idx1] = 0;
flag = true;
}
else if (MAP[i][j] == MAP[i][idx2]) {
TEMP[i][j] = 0;
TEMP[i][idx2] = 0;
flag = true;
}
else if (MAP[i][j] == MAP[i + 1][j]) {
TEMP[i][j] = 0;
TEMP[i + 1][j] = 0;
flag = true;
}
}
else if (i == n) {
int idx1 = j - 1;
int idx2 = j + 1;
if (idx1 == 0) idx1 = m;
if (idx2 == m + 1) idx2 = 1;
if (MAP[i][j] == MAP[i][idx1]) {
TEMP[i][j] = 0;
TEMP[i][idx1] = 0;
flag = true;
}
else if (MAP[i][j] == MAP[i][idx2]) {
TEMP[i][j] = 0;
TEMP[i][idx2] = 0;
flag = true;
}
else if (MAP[i][j] == MAP[i - 1][j]) {
TEMP[i][j] = 0;
TEMP[i - 1][j] = 0;
flag = true;
}
}
else {
int idx1 = j - 1;
int idx2 = j + 1;
if (idx1 == 0) idx1 = m;
if (idx2 == m + 1) idx2 = 1;
if (MAP[i][j] == MAP[i][idx1]) {
TEMP[i][j] = 0;
TEMP[i][idx1] = 0;
flag = true;
}
else if (MAP[i][j] == MAP[i][idx2]) {
TEMP[i][j] = 0;
TEMP[i][idx2] = 0;
flag = true;
}
else if (MAP[i][j] == MAP[i + 1][j]) {
TEMP[i][j] = 0;
TEMP[i + 1][j] = 0;
flag = true;
}
else if (MAP[i][j] == MAP[i - 1][j]) {
TEMP[i][j] = 0;
TEMP[i - 1][j] = 0;
flag = true;
}
}
}
}
if (flag) return true;
else return false;
}
void solve() {
int cnt = 0;
int sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (TEMP[i][j] != 0) {
sum += TEMP[i][j];
cnt++;
}
}
}
double avg = (double)sum / cnt;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (TEMP[i][j] > avg) {
TEMP[i][j]--;
}
else if (TEMP[i][j] < avg && TEMP[i][j] > 0) {
TEMP[i][j]++;
}
}
}
}
void answer_count() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (MAP[i][j] != 0) {
ans += MAP[i][j];
}
}
}
cout << ans;
}
void INPUT() {
cin >> n >> m >> t;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> MAP[i][j];
}
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
INPUT();
for (int i = 0; i < t; i++) {
move(x, d, K);
setting();
if (!remove()) solve();
setting1();
}
answer_count();
return 0;
}
