백준 g2 17822 원판 돌리기 c++

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

17822번: 원판 돌리기

 

문제 설명

1. 1~N번의 원판에 M개의 숫자가 있다.
2. T번, x배수의 원판을 d방향으로 k칸 만큼 돌릴 수 있다.
3. 이때, 인접하면서 같은 수가 있으면 모두 지운다.
   1. 없는 경우에는 평균을 구한 다음 평균보다 큰 수는 +1, 작은 수는 -1

풀이

 

1. 원판

board[N][M]: 원판에 적혀있는 숫자들 정보, x배수를 써야하기 때문에 N은 1~N, M은 나머지 연산 쓰기 유용하도록 0~M-1

cursor[N]: 1~N번 원판에서 맨 처음이 몇 번째 칸인지 알려주는 배열, 여기서 맨 처음은 제일 위에 있는 칸으로 한다

                - 만약 시계방향으로 한 칸 돌리면, M-1이 제일 위로 오게 되므로 cursor--

                - 반대로 반시계방향으로 한 칸 돌리면, 2가 제일 위로 오게 되므로 cursor++

erase[N][M]: 여러 칸이 붙어 있는 경우에, 그때 그때 지워버리면 도달하지 못하는 칸이 있을 수 있으므로 erase 배열에 저장해놨다가 한번에 지우도록 한다.

ex. 2 2 2 가 붙어있을 때

제일 앞에 2부터 시작하므로 첫번째 2, 두번째 2가 같다고 체크된다. 여기서 이 둘을 지워버리면 세번째 2는 지워져야함에도 불구하고 지워지지 않으므로 오류가 생김

 

2. 원판 회전하기

 

음수가 될 수 있으므로 M을 더해준다. k<M이기 때문에 M을 더해주면 무조건 양수가 된다.

    for (int i = x; i <= N; i += x) {
        if (d == 0) {
            cursor[i] = ((cursor[i] - k) + M) % M;
        } else if (d == 1) {
            cursor[i] = ((cursor[i] + k)) % M;
        }
    }

 

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

 

현재 보고 있는 숫자를 board[i][j]라고 했을 때, 

양 옆의 숫자는 (i, j-1) (i, j+1)을 구하면 된다.

 

위아래로 인접한 숫자를 구할 때는

nj = (cursor[ni] - cursor[i] + j + M) % M

 

현재 i번 판과 ni번 판의 차이를 구한 다음에, 그 차이만큼 j칸 옮기면 된다. 

for (int i = 1; i <= N; i++) {
        for (int j = 0; j < M; j++) {
            int val = board[i][j];
            if (val == -99) continue;
            
            // 2-1. board(i, j)의 양 옆
            int nj = ((j - 1) + M) % M;
            if (val == board[i][nj]) {
                erase[i][j] = true;
                erase[i][nj] = true;
                exist = true;
            }

            nj = (j + 1) % M;
            if (val == board[i][nj]) {
                erase[i][j] = true;
                erase[i][nj] = true;
                exist = true;
            }

            // 2-2. 위 아래 원판 board(i+-1, j) cursor: 위 - 아래

            // 2-2-1. 윗 원판
            if (i != N) {
                int ni = i + 1;
                if (ni == N + 1) ni = 1;
                nj = (cursor[ni] - cursor[i] + j + M) % M;

                if (val == board[ni][nj]) {
                    erase[i][j] = true;
                    erase[ni][nj] = true;
                    exist = true;
                }
            }

            // 2-2-2. 아래 원판
            if (i != 1) {
                int ni = i - 1;
                if (ni == 0) ni = N;
                nj = (cursor[ni] - cursor[i] + j + M) % M;

                if (val == board[ni][nj]) {
                    erase[i][j] = true;
                    erase[ni][nj] = true;
                    exist = true;
                }
            }
        }
    }

 

 

전체 코드

/*boj g2 17822 원판 돌리기*/
#include <iostream>
#define MAXN 55
using namespace std;

int N, M, T;
int board[MAXN][MAXN]; // 반지름 1~N, 칸 0~M-1
int cursor[MAXN];

bool erase[MAXN][MAXN];

void print() {
    cout << "\n====================\n";
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < M; j++) {
            cout << board[i][j] << " ";
        }
        cout << "\n";
    }
}

void input() {
    cin >> N >> M >> T;

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> board[i][j];
        }
    }
}

void turn(int x, int d, int k) {
    // 1. 번호가 x의 배수인 원판을 d방향으로 k칸 회전
    for (int i = x; i <= N; i += x) {
        if (d == 0) {
            cursor[i] = ((cursor[i] - k) + M) % M;
        } else if (d == 1) {
            cursor[i] = ((cursor[i] + k)) % M;
        }
    }
    // 2. 인접하면서 수가 같은 것 찾기
    bool exist = false;

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < M; j++) {
            int val = board[i][j];
            if (val == -99) continue;
            // 2-1. board(i, j)의 양 옆
            int nj = ((j - 1) + M) % M;
            if (val == board[i][nj]) {
                erase[i][j] = true;
                erase[i][nj] = true;
                exist = true;
            }

            nj = (j + 1) % M;
            if (val == board[i][nj]) {
                erase[i][j] = true;
                erase[i][nj] = true;
                exist = true;
            }

            // 2-2. 위 아래 원판 board(i+-1, j) cursor: 위 - 아래

            // 2-2-1. 윗 원판
            if (i != N) {
                int ni = i + 1;
                if (ni == N + 1) ni = 1;
                nj = (cursor[ni] - cursor[i] + j + M) % M;

                if (val == board[ni][nj]) {
                    erase[i][j] = true;
                    erase[ni][nj] = true;
                    exist = true;
                }
            }

            // 2-2-2. 아래 원판
            if (i != 1) {
                int ni = i - 1;
                if (ni == 0) ni = N;
                nj = (cursor[ni] - cursor[i] + j + M) % M;

                if (val == board[ni][nj]) {
                    erase[i][j] = true;
                    erase[ni][nj] = true;
                    exist = true;
                }
            }
        }
    }

    for (int i = 1; i <= N; i++)
        for (int j = 0; j < M; j++) {
            if (erase[i][j] == true)
                board[i][j] = -99;
        }

    // 3. 인접하면서 같은 수가 없으면, 원판에 적힌 수의 평균을 구하고 +-1
    if (exist) return;
    int sum = 0;
    int cnt = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == -99) continue;

            sum += board[i][j];
            cnt++;
        }
    }
    double avg = (double)sum / cnt;
    // cout << avg << "\n";
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == -99) continue;
            if (board[i][j] < avg)
                board[i][j]++;
            else if (board[i][j] > avg)
                board[i][j]--;
        }
    }
}

void output() {
    int sum = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == -99) continue;

            sum += board[i][j];
        }
    }
    cout << sum << "\n";
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();

    while (T--) {
        int x, d, k;
        cin >> x >> d >> k;

        turn(x, d, k);
    }

    // print();
    output();
}