[백준] 17822번 원판 돌리기

17822번 원판 돌리기

---

1. 이해하기

• 원판의 회전은 독립적으로 이루어진다.
• 원판을 회전시킬 때는 수의 위치를 기준으로 한다.
• 원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi,di,ki이다.
  1. 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
  2. 인접하면서 수가 같은 것을 모두 찾는다.
     1. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
     2. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.
• 원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구하는 문제.
• 시뮬레이션 문제.

---

2. 구현하기

• 원판을 시계방향, 반시계방향으로 회전시켰을 때를 구현한다.

  void rotate_clock(int n, int cnt) {
      for(int i = 1; i <= N; i++) {
          if(i%n == 0) {
              for(int k = 0; k < cnt; k++) {
                  int t = disc[i][M-1];
                  for(int j = M-1; j-1 >= 0; j--) {
                      disc[i][j] = disc[i][j-1];
                  }
                  disc[i][0] = t;
              }
          }
      }
  }
  
  void rotate_anticlock(int n, int cnt) {
      for(int i = 1; i <= N; i++) {
          if(i%n == 0) {
              for(int k = 0; k < cnt; k++) {
                  int t = disc[i][0];
                  for(int j = 0; j+1 < M; j++) {
                      disc[i][j] = disc[i][j+1];
                  }
                  disc[i][M-1] = t;
              }
          }
      }
  }

• 회전시킨후, 인접한 수들은 모두 지워준다.

  • 지워줄 수들을 저장할 벡터를 따로 만들어서 저장한다.
  • 지워줄 수가 없다면 false를 리턴한다. 다음에 보정을 할지를 결정해야하기 때문이다.

  bool delete_num() {
      vector<Point> v;
      for(int i = 1; i <= N; i++) {
          for(int j = 0; j < M; j++) {
              if(disc[i][j] == 0) continue;
              if(disc[i][j] == disc[i][(j+1)%M]) {
                  v.push_back({i,j});
                  v.push_back({i,(j+1)%M});
              }
          }
      }
      for(int j = 0; j < M; j++) {
          for(int i = 1; i+1 <= N; i++) {
              if(disc[i][j] == 0) continue;
              if(disc[i][j] == disc[i+1][j]) {
                  v.push_back({i,j});
                  v.push_back({i+1,j});
              }
          }
      }
  
      if(v.size() == 0) return false;
      int size = v.size();
      for(int i = 0; i < size; i++) {
          Point now = v[i];
          disc[now.i][now.j] = 0;
      }
      return true;
  }

• 지워줄 수가 없었다면 보정작업을 해준다.

  void bojung() {
      int sum = 0, cnt = 0;
      for(int i = 1; i<= N; i++) {
          for(int j = 0; j < M; j++) {
              if(disc[i][j] != 0) {
                  cnt++;
                  sum+=disc[i][j];
              }
          }
      }
      if(cnt == 0) return;
      double ave = (double)sum/cnt;
      for(int i = 1; i <= N; i++) {
          for(int j = 0; j < M; j++) {
              if(disc[i][j] == 0) continue;
              if(disc[i][j] > ave) {
                  disc[i][j]--;
              } else if(disc[i][j] < ave) {
                  disc[i][j]++;
              }
          }
      }
  }

• T번의 시뮬레이션을 하고 남은 원판의 수들의 합을 구해준다.

  void simulate() {
      for(int t = 0; t < T; t++) {
          int x,d,k;
          cin >> x >> d >> k;
          if(d == 0) rotate_clock(x,k);
          else rotate_anticlock(x,k);
          if(!delete_num()) bojung();
      }
  }
  
  int get_sum() {
      int ret = 0;
      for(int i = 1; i <= N; i++) {
          for(int j = 0; j < M; j++) {
              ret += disc[i][j];
          }
      }
      return ret;
  }

---

3. 전체 코드

#include <iostream>
#include <vector>
using namespace std;
struct Point {
    int i,j;
};
int disc[51][50];
int N,M,T;

void rotate_clock(int n, int cnt) {
    for(int i = 1; i <= N; i++) {
        if(i%n == 0) {
            for(int k = 0; k < cnt; k++) {
                int t = disc[i][M-1];
                for(int j = M-1; j-1 >= 0; j--) {
                    disc[i][j] = disc[i][j-1];
                }
                disc[i][0] = t;
            }
        }
    }
}

void rotate_anticlock(int n, int cnt) {
    for(int i = 1; i <= N; i++) {
        if(i%n == 0) {
            for(int k = 0; k < cnt; k++) {
                int t = disc[i][0];
                for(int j = 0; j+1 < M; j++) {
                    disc[i][j] = disc[i][j+1];
                }
                disc[i][M-1] = t;
            }
        }
    }
}

bool delete_num() {
    vector<Point> v;
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j < M; j++) {
            if(disc[i][j] == 0) continue;
            if(disc[i][j] == disc[i][(j+1)%M]) {
                v.push_back({i,j});
                v.push_back({i,(j+1)%M});
            }
        }
    }
    for(int j = 0; j < M; j++) {
        for(int i = 1; i+1 <= N; i++) {
            if(disc[i][j] == 0) continue;
            if(disc[i][j] == disc[i+1][j]) {
                v.push_back({i,j});
                v.push_back({i+1,j});
            }
        }
    }

    if(v.size() == 0) return false;
    int size = v.size();
    for(int i = 0; i < size; i++) {
        Point now = v[i];
        disc[now.i][now.j] = 0;
    }
    return true;
}

void bojung() {
    int sum = 0, cnt = 0;
    for(int i = 1; i<= N; i++) {
        for(int j = 0; j < M; j++) {
            if(disc[i][j] != 0) {
                cnt++;
                sum+=disc[i][j];
            }
        }
    }
    if(cnt == 0) return;
    double ave = (double)sum/cnt;
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j < M; j++) {
            if(disc[i][j] == 0) continue;
            if(disc[i][j] > ave) {
                disc[i][j]--;
            } else if(disc[i][j] < ave) {
                disc[i][j]++;
            }
        }
    }
}

void simulate() {
    for(int t = 0; t < T; t++) {
        int x,d,k;
        cin >> x >> d >> k;
        if(d == 0) rotate_clock(x,k);
        else rotate_anticlock(x,k);
        if(!delete_num()) bojung();
    }
}

int get_sum() {
    int ret = 0;
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j < M; j++) {
            ret += disc[i][j];
        }
    }
    return ret;
}

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

int main() {
    input();
    simulate();
    cout << get_sum() << '\n';
    return 0;
}

---

4. 뒷 이야기

• 시험을 볼때는 보정작업을 할 때, 평균값을 어떻게 구하는지에 대한 조건이 따로 있었던 것으로 기억한다. 기억하기론 소수점을 버린다는 것으로 기억한다.
• 아니면... 틀린거겠지...