이번에는 백준 17822번 원판 돌리기 문제를 풀어보았습니다.
각 원판을 조건에 따라 회전시킨 뒤, 인접하면서 같은 숫자가 있는지 확인하고, 존재한다면 해당 숫자들을 모두 삭제해야 합니다.
반대로 같은 숫자가 하나도 없다면 현재 남아 있는 숫자들의 평균을 기준으로 값을 조정해야 합니다.
따라서 문제에서 주어진 순서를 그대로 구현하는 시뮬레이션 방식으로 해결하였습니다.
문제 설명
총 N개의 원판이 있고, 각 원판에는 M개의 숫자가 원형으로 배치되어 있습니다.
각 회전 명령 (x, d, k)마다 다음 작업을 수행합니다.
- 번호가
x의 배수인 원판을d방향으로k칸 회전합니다. - 인접하면서 같은 숫자가 있는지 확인합니다.
- 같은 숫자가 있다면 해당 숫자들을 모두 삭제합니다.
- 같은 숫자가 없다면 현재 남아 있는 숫자들의 평균을 구합니다.
- 평균보다 큰 숫자는 1 감소시키고, 평균보다 작은 숫자는 1 증가시킵니다.
모든 회전이 끝난 뒤 남아 있는 숫자들의 합을 구하는 문제입니다.
풀이 아이디어
원판의 숫자를 다음과 같은 2차원 배열에 저장하였습니다.
int circle[51][51];circle[i][j]는 i번째 원판의 j번째 위치에 있는 숫자를 의미합니다.
삭제된 숫자는 0으로 처리하였습니다.
각 회전 명령마다 먼저 조건에 해당하는 원판을 회전시킵니다.
이후 인접한 숫자를 다음 두 방향으로 확인합니다.
위아래 원판 사이
같은 원판 내부의 좌우같은 숫자를 발견하면 즉시 삭제하지 않고
find_target배열에 삭제할 위치를 표시합니다.
모든 비교가 끝난 후 한 번에 삭제해야, 먼저 삭제된 값 때문에 뒤의 비교가 영향을 받지 않습니다.
같은 숫자가 하나도 없다면 현재 남아 있는 숫자의 합과 개수를 이용하여 평균과 비교합니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N,M,T;
int circle[51][51];
bool find_target[51][51];
void rotate_circle(int idx, int how, int dir) {
int temp[51];
if (dir == 0) {
for (int i=0; i<M; i++) {
temp[(i+how)%M] = circle[idx][i];
}
} else {
for (int i=0; i<M; i++) {
temp[i] = circle[idx][(i+how)%M];
}
}
memcpy(circle[idx], temp, sizeof(int) * M);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M >> T;
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
cin >> circle[i][j];
}
}
for (int i=0; i<T; i++) {
int x,d,k;
cin >> x >> d >> k;
for (int j=1; j<=N; j++) {
if (j%x == 0)
rotate_circle(j-1,k,d);
}
bool is_find = false;
for (int j=1; j<N; j++) {
for (int l=0; l<M; l++) {
if (circle[j][l] == 0) continue;
if (circle[j][l] == circle[j-1][l] ) {
find_target[j][l] = true;
find_target[j-1][l] = true;
is_find = true;
}
}
}
for (int j=0; j<N; j++) {
for (int l=0; l<M; l++) {
if (circle[j][l] == 0) continue;
if (l != M-1) {
if (circle[j][l] == circle[j][l+1]) {
find_target[j][l] = true;
find_target[j][l+1] = true;
is_find = true;
}
} else {
if (circle[j][M-1] == circle[j][0]) {
find_target[j][M-1] = true;
find_target[j][0] = true;
is_find = true;
}
}
}
}
if (!is_find) {
long long sum=0;
int cnt=0;
for (int j=0; j<N; j++) {
for (int l=0; l<M; l++) {
if (circle[j][l] == 0) continue;
cnt++;
sum += circle[j][l];
}
}
for (int j=0; j<N; j++) {
for (int l=0; l<M; l++) {
if (circle[j][l] == 0) continue;
if (sum > circle[j][l] * cnt) {
circle[j][l] += 1;
} else if (sum < circle[j][l] * cnt) {
circle[j][l] -= 1;
}
}
}
} else {
for (int j=0; j<N; j++) {
for (int l=0; l<M; l++) {
if (find_target[j][l])
circle[j][l] = 0;
}
}
}
memset(find_target, false, sizeof(find_target));
}
int sum=0;
for (int i=0; i<N; i++) {
for (int j=0;j<M; j++) {
sum += circle[i][j];
}
}
cout << sum;
return 0;
}풀이 흐름
-
각 원판의 숫자를
circle배열에 저장합니다. -
총
T번의 회전 명령을 순서대로 처리합니다. -
현재 명령의
x의 배수에 해당하는 원판을 회전시킵니다. -
서로 다른 원판에서 같은 위치에 있는 숫자를 비교합니다.
-
같은 원판 안에서는 좌우로 인접한 숫자를 비교합니다.
-
원판은 원형이므로 마지막 위치와 첫 번째 위치도 비교합니다.
-
같은 숫자가 존재하면 해당 위치를
find_target에 표시합니다. -
비교가 끝난 뒤 표시된 숫자를 모두 0으로 변경하여 삭제합니다.
-
같은 숫자가 하나도 없다면 남아 있는 숫자의 평균을 계산합니다.
-
평균보다 작은 숫자는 1 증가시키고, 큰 숫자는 1 감소시킵니다.
-
모든 회전이 끝난 뒤 원판에 남아 있는 숫자의 합을 출력합니다.
구현 포인트
1. 원판 상태 저장
int circle[51][51];각 행을 하나의 원판으로 생각하였습니다.
circle[0] : 1번 원판
circle[1] : 2번 원판
...각 열은 원판 위의 위치를 의미합니다.
삭제된 숫자는 0으로 변경하여 관리하였습니다.
2. 원판 회전
void rotate_circle(int idx, int how, int dir)idx번째 원판을 how칸만큼 dir 방향으로 회전합니다.
임시 배열에 회전 결과를 저장한 뒤 다시 원래 원판에 복사합니다.
3. 시계 방향 회전
if (dir == 0) {
for (int i=0; i<M; i++) {
temp[(i+how)%M] = circle[idx][i];
}
}시계 방향으로 how칸 회전하면 기존 i번째 위치의 숫자가
(i + how) % M위치로 이동합니다.
예를 들어 M = 4, how = 1이라면
0 → 1
1 → 2
2 → 3
3 → 0으로 이동합니다.
마지막 위치가 다시 첫 번째 위치로 이어져야 하므로 % M을 사용합니다.
4. 반시계 방향 회전
else {
for (int i=0; i<M; i++) {
temp[i] = circle[idx][(i+how)%M];
}
}반시계 방향으로 how칸 회전하면 새로운 i번째 위치에는 기존의
(i + how) % M위치에 있던 값이 들어오게 됩니다.
이를 통해 별도의 방향 배열 없이 인덱스 계산만으로 원판을 회전시켰습니다.
5. x의 배수인 원판만 회전
for (int j=1; j<=N; j++) {
if (j%x == 0)
rotate_circle(j-1,k,d);
}문제에서 원판 번호는 1부터 시작하므로 반복문도 1부터 N까지 사용합니다.
현재 원판 번호 j가 x로 나누어떨어지는 경우에만 회전시킵니다.
실제 배열은 0부터 시작하므로
j - 1을 인덱스로 사용합니다.
6. 인접한 숫자 표시 배열
bool find_target[51][51];같은 숫자를 발견했다고 해서 바로 0으로 변경하지 않습니다.
먼저 삭제해야 할 위치만 true로 표시합니다.
find_target[j][l] = true;모든 인접 관계를 확인한 뒤 한 번에 삭제합니다.
이렇게 해야 같은 회전 단계에서 원래 존재했던 숫자를 기준으로 모든 인접 관계를 정확하게 확인할 수 있습니다.
7. 다른 원판과의 인접 관계
같은 위치에 있으면서 원판 번호가 하나 차이나면 서로 인접합니다.
for (int j=1; j<N; j++) {
for (int l=0; l<M; l++) {현재 원판 j와 바로 안쪽 원판 j-1의 같은 위치를 비교합니다.
if (circle[j][l] == circle[j-1][l]) {두 값이 같다면 모두 삭제 대상입니다.
find_target[j][l] = true;
find_target[j-1][l] = true;
is_find = true;8. 삭제된 숫자는 비교하지 않음
if (circle[j][l] == 0) continue;삭제된 숫자는 0으로 저장되어 있습니다.
0끼리 같다고 해서 삭제 대상으로 판단하면 안 되므로 현재 숫자가 0이라면 비교하지 않고 넘어갑니다.
9. 같은 원판 내부의 인접 관계
같은 원판에서는 현재 위치의 오른쪽 숫자를 확인합니다.
if (circle[j][l] == circle[j][l+1]) {같은 숫자라면 두 위치를 모두 삭제 대상으로 표시합니다.
find_target[j][l] = true;
find_target[j][l+1] = true;10. 원판의 처음과 끝 연결
원판은 원형이므로 마지막 숫자와 첫 번째 숫자도 서로 인접합니다.
if (l != M-1) {일반적인 위치에서는 l+1을 확인하지만, 마지막 위치라면 첫 번째 위치와 비교합니다.
if (circle[j][M-1] == circle[j][0]) {
find_target[j][M-1] = true;
find_target[j][0] = true;
is_find = true;
}이 부분으로 원판의 원형 구조를 처리하였습니다.
11. 같은 숫자가 하나라도 존재하는지 확인
bool is_find = false;인접하면서 같은 숫자를 하나라도 발견하면
is_find = true;로 변경합니다.
이 값에 따라 이후 처리가 달라집니다.
같은 숫자 존재 → 해당 숫자 삭제
같은 숫자 없음 → 평균을 기준으로 값 변경12. 같은 숫자를 한 번에 삭제
if (find_target[j][l])
circle[j][l] = 0;모든 비교가 끝난 뒤 find_target이 true인 위치를 0으로 변경합니다.
예를 들어 같은 숫자가 세 칸 연속으로 존재한다면 비교 과정에서 세 위치 모두 표시되고, 마지막에 전부 동시에 삭제됩니다.
13. 같은 숫자가 없는 경우 평균 계산
if (!is_find) {
long long sum=0;
int cnt=0;삭제할 숫자가 하나도 없다면 현재 원판에 남아 있는 숫자의 합과 개수를 구합니다.
if (circle[j][l] == 0) continue;
cnt++;
sum += circle[j][l];삭제된 숫자는 평균 계산에서 제외합니다.
14. 실수 연산 없이 평균과 비교
평균은
sum / cnt입니다.
하지만 코드에서는 직접 나눗셈을 수행하지 않고 다음과 같이 비교하였습니다.
if (sum > circle[j][l] * cnt)이는
sum / cnt > circle[j][l]과 같은 의미입니다.
즉, 현재 숫자가 평균보다 작다면
circle[j][l] += 1;을 수행합니다.
반대로
else if (sum < circle[j][l] * cnt)라면 현재 숫자가 평균보다 큰 것이므로
circle[j][l] -= 1;을 수행합니다.
이 방식으로 double을 사용하지 않고도 평균과 정확하게 비교할 수 있습니다.
15. 평균과 같은 경우
현재 숫자가 평균과 정확히 같다면
sum == circle[j][l] * cnt가 됩니다.
이 경우에는 if, else if 어디에도 해당하지 않으므로 값을 변경하지 않습니다.
문제에서 요구하는 동작과 같습니다.
16. 삭제 대상 배열 초기화
한 번의 회전 처리가 끝나면 다음 회전에 영향을 주지 않도록 배열을 초기화합니다.
memset(find_target, false, sizeof(find_target));따라서 각 회전 명령마다 새롭게 삭제할 숫자를 찾게 됩니다.
17. 문제의 처리 순서 그대로 구현
각 회전 명령에서는 반드시 다음 순서로 동작해야 합니다.
원판 회전
→ 같은 숫자 탐색
→ 같은 숫자가 있으면 삭제
→ 없다면 평균 계산 후 값 변경현재 코드에서도 이 순서대로 처리하고 있습니다.
시뮬레이션 문제에서는 동작 순서가 달라지면 결과도 달라질 수 있기 때문에 문제에서 주어진 순서를 그대로 구현하는 것이 중요합니다.
시간복잡도
한 번의 명령에서 먼저 최대 N개의 원판을 회전합니다.
각 원판을 회전하는 데 O(M)이 필요하므로
O(N × M)입니다.
이후 인접한 숫자를 확인하고, 필요하다면 삭제하거나 평균에 따라 값을 변경하는 과정 역시 전체 N × M개의 위치를 순회합니다.
따라서 한 번의 회전 명령에 필요한 시간복잡도는
O(N × M)이고, 이를 총 T번 수행하므로 전체 시간복잡도는
O(T × N × M)입니다.
N, M, T의 범위에서 충분히 해결할 수 있습니다.
