https://www.acmicpc.net/problem/17140
17140번: 이차원 배열과 연산
첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.
www.acmicpc.net
초기 배열의 크기가 3X3이고 1초가 지날 때마다 배열에 연산이 적용되는데
최종적으로 배열의 r행c열에 들어있는 값이 k가 되는 시간을 찾는 문제이다.
시간이 100을 넘어가는 경우에는 -1을 출력한다.
R연산과 C연산은 다음과 같다.
- R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
- C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.
이 문제에서 중요한 부분은 각 숫자의 등장 횟수를 센다음에 어떻게 새로 저장해 주느냐인 것 같다.
나는 벡터를 이용해서 저장했다. 벡터의 자료 형을 pair로 넣고 정렬할 경우
pair 중 앞부분 우선으로 먼저 정렬되고 그다음에 두 번째 걸로 정렬되는 점을 이용했다.
이 문제에서는 먼저 수의 등장 횟수순으로 정렬되어야 하기 때문에 등장 횟수를 앞에 넣어주고 수를
뒤에 넣어주었다. 그리고 다시 배열에 저장할때는 벡터의 뒤에 거를 먼저 빼서 넣어주고 앞에 거를 넣어줬다.
그리고 또 중요한 것은 바뀌는 행의 크기와 열의 크기이다.
매번 연산때마다 크기는 줄어들거나 커질 수 있는데 해당 연산에서의 최댓값으로 다시 갱신해주어야 한다.
자세한 설명은 코드의 R연산(rcalc) 부분을 참고!
C연산은 R연산을 열 기준으로 바꿔주면 되므로 생략했다.
|
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int map[150][150];
int cnt[101];
int r, c, k;
int rsize, csize;
vector<pair<int, int>> vt;
void c_calc() {
int new_rsize = 0;
for (int i = 0; i < csize; i++) {
for (int j = 0; j < rsize; j++) {
cnt[map[j][i]]++;
}
for (int k = 1; k <= 100; k++) {
if (cnt[k] != 0) {
vt.push_back(make_pair(cnt[k], k));
cnt[k] = 0;
}
}
sort(vt.begin(), vt.end());
int vtsize = vt.size();
int newsize = vtsize * 2;
new_rsize = max(new_rsize, newsize);
int index = 0;
for (int k = 0; k < newsize; k += 2) {
map[k][i] = vt.at(index).second;
map[k + 1][i] = vt.at(index).first;
index++;
}
for (int k = newsize; k < rsize; k++) {
map[k][i] = 0;
}
vt.clear();
}
rsize = new_rsize;
}
void rcalc() {
int new_csize = 0; //이번 연산에서 새로 바뀔 열 크기 중 최댓값이 저장된다.
//모든 행에 대해서 R연산을 해준다.
for (int i = 0; i < rsize; i++) {
//숫자의 등장 횟수를 세기 위해서, 각 열의 숫자를 인덱스로 cnt배열의 값을 증가시킨다.
for (int j = 0; j < csize; j++) {
cnt[map[i][j]]++;
}
//개수가 0개가 아니라면 벡터에 넣어주고 cnt배열은 다시 0으로 초기화 해준다.
for (int k = 1; k <= 100; k++) {
if (cnt[k] != 0) {
//수의 등장횟수로 먼저 정렬되므로 수의 등장횟수를 앞에 넣어주고
//해당 수를 뒤에 넣어준다.
vt.push_back(make_pair(cnt[k], k));
cnt[k] = 0;
}
}
//정렬
sort(vt.begin(), vt.end());
//쌍으로 벡터에 들어가있으므로 하나씩 꺼내주기 위해 2를 곱해준다.
int vtsize = vt.size();
int newsize = vtsize * 2;
//현재 연산의 최대 열 길이(new_csize가 이번 연산이 끝나면 csize(열 사이즈)로 바뀐다)
new_csize = max(new_csize, newsize);
//map에 다시 넣어준다.
int index = 0;
for (int k = 0; k < newsize; k += 2) {
//수를 뒤에 넣었으므로 두번째 값(second)을 먼저 꺼낸다.
map[i][k] = vt.at(index).second;
//수의 등장 횟수를 앞(first)에 넣어놨으므로 나중에 꺼낸다.
map[i][k + 1] = vt.at(index).first;
index++;
}
//숫자를 채우고 남은 칸을 0으로 채워준다. (열 크기까지)
for (int k = newsize; k < csize; k++) {
map[i][k] = 0;
}
//벡터 정리
vt.clear();
}
//열 크기는 이번 연산에서 가장 긴 열의 크기로 바뀐다
//(줄어들 수 도 있고 늘어날 수 도 있음)
csize = new_csize;
}
void solve() {
int time = 0;
while (true) {
//찾은 경우
if (map[r][c] == k) {
cout << time << '\n';
break;
}
time++;
//시간이 100을 넘어가는 경우
if (time > 100) {
cout << -1 << '\n';
break;
}
//R연산
if (rsize >= csize) {
rcalc();
}
else {//C연산
c_calc();
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> r >> c >> k;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cin >> map[i][j];
}
}
//index가 0번부터 시작하므로 1씩 빼준다.
r--;
c--;
rsize = 3;
csize = 3;
solve();
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 16236. 아기 상어 (0) | 2019.07.31 |
|---|---|
| [BOJ] 17144. 미세먼지 안녕! (0) | 2019.07.30 |
| [BOJ] 17142. 연구소 3 (0) | 2019.07.30 |
| [BOJ] 1806. 부분합 (0) | 2019.07.16 |
| [BOJ] 2003. 수들의 합 2 (0) | 2019.07.15 |