17822번: 원판 돌리기 
문제 링크: 17822번: 원판 돌리기
개요
시키는 대로 구현만 잘 하면 되는 시뮬레이션 문제이다. n(원판의 개수), m(한 원판 안의 숫자 개수), k(원판 회전 횟수)가 최대 50으로 작기 때문에 회전을 직접 이동시켜서 구현해도 시간초과가 발생하지 않을 듯 하지만(*진위여부 파악 필요) 나는 원판을 회전시키지 않고 각 원판이 얼마나 회전된 상태인지를 따로 저장한 값으로 매번 인덱스를 보정하여 사용하는 방법으로 회전을 구현했다.
사용하는 배열들을 굳이 동적 할당으로 할당받아야 할 이유는 없지만 단순히 연습을 위해 동적 할당을 이용했다. 동적 할당 시 마지막에 메모리 해제하는 것을 잊지 말자.
회전 구현
1차원 int형 배열 rot의 0번 위치부터 n-1번 위치까지를 (n+1)번째 판이 회전된 정도를 저장하는 데에 사용했다.
1
2
3
4
5
6
7
int xi, di, ki;
scanf("%d %d %d", &xi, &di, &ki);
di = di * 2 - 1;
for (int x = xi; x <= n; x+=xi) {
rot[x-1] += di * ki + m;
rot[x - 1] %= m;
}
di는 시계방향일 때 0, 반시계방향일 때 1이 입력되는데 시계방향일 때 -1, 반시계방향일 때 1로 만들고 싶기 때문에 (di * 2 - 1)로 바꿔주었다. 방향을 나타내는 di와 회전 칸수를 나타내는 ki를 곱해 rot 배열의 해당 위치에 더해준다. 이 때 한 원판의 숫자 개수를 나타내는 m을 더한 후 다시 m으로 모듈러 연산을 해주었는데 이렇게 하지 않으면 int 오버플로우가 발생하여(*추정) 0%에서 ‘틀렸습니다!’가 나온다. (이것 때문에 시간을 무진장 많이 잡아먹었다.)
1
2
3
int rotdY(int x, int y) {
return (y + m + rot[x]) % m;
}
보정할 값을 저장했으면 해당 값으로 인덱스를 보정해주어야 한다. 코드의 간결함을 위해 함수로 분리해서 사용했다. arr[i][j]에 접근할 때 항상 arr[i][(rotdY[i], j)] 꼴로 사용했다.
인접한 같은 숫자 삭제하기 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int deleteSameNum(int x0, int y0, int vstd[][50], int depth) {
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
if (!exist[x0][rotdY(x0, y0)] || vstd[x0][rotdY(x0, y0)]) return 0;
int existSame = 0;
vstd[x0][rotdY(x0, y0)] = 1;
for (int d = 0; d < 4; d++) {
int x = x0 + dx[d];
int y = y0 + dy[d];
if (x >= 0 && x < n && arr[x0][rotdY(x0, y0)] == arr[x][rotdY(x, y)]) {
existSame = 1;
deleteSameNum(x, y, vstd, depth + 1);
}
}
if (depth || existSame) arr[x0][rotdY(x0, y0)] = 0, exist[x0][rotdY(x0, y0)] = 0;
return existSame;
}
일반적인 dfs로 구현했다. 2차원 배열에서 인접한 수를 탐색하는 것과 방법은 같지만 이 문제에서는 시작과 끝이 연결된 원형이기 때문에 가로방향 인덱스는 보정된 값을 사용하고, 한계 조건을 걸지 않았다는 차이가 있다. 깊이가 0일 때는 상하좌우 중 한 곳 이상에 같은 값이 있을 때만, 깊이가 1 이상일 때는 조건 상관 없이 해당 숫자를 삭제하고 숫자의 존재 여부를 체크하는 배열 exist의 해당 위치를 0으로 바꿔주었다.
유의사항
- 원판을 회전시킬 때, 입력받은 원판 번호(xi)의 배수인 원판을 모두 회전시켜야 하기 때문에 for (int x = xi; x <= n; x+=xi) 와 같은 형태의 반복문을 사용했다. for (int x = xi; x <= n; x+=x) 와 같이 자기 자신을 다시 더하면 안 된다.
- 원본 삼성 역량테스트 기출 문제에서는 평균 값을 내림하여 사용했지만 이 문제에서는 내림하지 않는다. 부동소수 자료형으로 저장해서 사용하자.
- 배열을 꼭 초기화 후 사용하자. 처음에 rot 배열을 초기화하지 않고 쓰레기값이 들어간 상태로 사용해서 엉뚱한 인덱스로 접근하는 일이 발생했다.
전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
int n, m, t, **arr, *rot, **exist;
int deleteSameNum(int, int, int [][50], int);
int rotdY(int, int);
double getAvg();
int main() {
scanf("%d %d %d", &n, &m, &t);
arr = malloc(sizeof(int *) * n);
if (arr == NULL) return -1;
exist = malloc(sizeof(int *) * n);
if (exist == NULL) return -1;
rot = malloc(sizeof(int) * n);
if (rot == NULL) return -1;
for (int i = 0; i < n; i++) {
arr[i] = malloc(sizeof(int) * m);
if (arr[i] == NULL) return -1;
exist[i] = malloc(sizeof(int) * m);
if (exist[i] == NULL) return -1;
for (int j = 0; j < m; j++) {
scanf("%d", &arr[i][j]);
exist[i][j] = 1;
}
rot[i] = 0;
}
for (int tc = 0; tc < t; tc++) {
int vstd[50][50] = { 0 };
int xi, di, ki;
scanf("%d %d %d", &xi, &di, &ki);
di = di * 2 - 1;
for (int x = xi; x <= n; x+=xi) {
rot[x-1] += di * ki + m;
rot[x - 1] %= m;
}
int existSame = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (deleteSameNum(i, j, vstd, 0)) existSame = 1;
}
}
if (!existSame) {
double avg = getAvg();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (exist[i][j] && arr[i][j] > avg) arr[i][j]--;
else if (exist[i][j] && arr[i][j] < avg) arr[i][j]++;
}
}
}
}
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (exist[i][rotdY(i, j)]) sum += arr[i][rotdY(i, j)];
}
}
printf("%d", sum);
for (int i = 0; i < n; i++) {
if (arr[i]) free(arr[i]);
if (exist[i]) free(exist[i]);
}
if (arr) free(arr);
if (exist) free(exist);
if (rot) free(rot);
return 0;
}
int deleteSameNum(int x0, int y0, int vstd[][50], int depth) {
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
if (!exist[x0][rotdY(x0, y0)] || vstd[x0][rotdY(x0, y0)]) return 0;
int existSame = 0;
vstd[x0][rotdY(x0, y0)] = 1;
for (int d = 0; d < 4; d++) {
int x = x0 + dx[d];
int y = y0 + dy[d];
if (x >= 0 && x < n && arr[x0][rotdY(x0, y0)] == arr[x][rotdY(x, y)]) {
existSame = 1;
deleteSameNum(x, y, vstd, depth + 1);
}
}
if (depth || existSame) arr[x0][rotdY(x0, y0)] = 0, exist[x0][rotdY(x0, y0)] = 0;
return existSame;
}
int rotdY(int x, int y) {
return (y + m + rot[x]) % m;
}
double getAvg() {
int cnt = 0, sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (exist[i][j]) cnt++, sum += arr[i][j];
}
}
if (!cnt) return 0.0;
return (double)sum / cnt;
}