문제
크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.
- R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
- C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.
한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.
예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.
정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.
행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.
배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.
입력
첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)
둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.
출력
A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.
풀이
생각보다 index가 꼬여서 햇갈린문제
다음과 같이 했다
R연산의 경우
각 행마다 R연산을 실행 했으며, vector에 빈도 , 숫자 이 순서로 push_back해주었다.
각 숫자의 빈도를 counting 하고, vector에 push, sort를 하면 순서가 맞는다.
그리고는 arr에 전달하는 과정이다.
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
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int R, C, K;
int row_count = 3;
int col_count = 3;
int arr[200][200];
int num_count[101];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> R >> C >> K;
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
cin >> arr[i][j];
int time = 0;
while (1) {
if (time > 100) {
cout << -1 << endl;
return 0;
}
if (arr[R][C] == K) {
cout << time << endl;
return 0;
}
else if (row_count >= col_count) {
// 연산 R
int max_size = 0;
for (int i = 1; i <= row_count; i++) {
vector<pair<int, int>> vec;
memset(num_count, 0, sizeof(num_count));
for (int j = 1; j <= col_count; j++)
num_count[arr[i][j]]++;
for (int j = 1; j <= 100; j++) {
if (num_count[j] == 0) {
continue;
}
vec.push_back(make_pair(num_count[j], j));
}
for (int j = 1; j <= col_count; j++)
arr[i][j] = 0;
sort(vec.begin(), vec.end());
int index = 1;
for (auto j : vec) {
arr[i][index++] = j.second;
arr[i][index++] = j.first;
if (index > 100)
break;
}
index--;
max_size = max(index, max_size);
}
col_count = max_size;
}
else if (row_count < col_count) {
// 연산 C
int max_size = 0;
for (int j = 1; j <= col_count; j++) {
vector<pair<int, int>> vec;
memset(num_count, 0, sizeof(num_count));
for (int i = 1; i <= row_count; i++)
num_count[arr[i][j]]++;
for (int i = 1; i <= 100; i++) {
if (num_count[i] == 0) {
arr[i][j] = 0;
continue;
}
vec.push_back(make_pair(num_count[i], i));
}
for (int i = 1; i <= row_count; i++)
arr[i][j] = 0;
sort(vec.begin(), vec.end());
int index = 1;
for (auto i : vec) {
arr[index++][j] = i.second;
arr[index++][j] = i.first;
if (index > 100)
break;
}
index--;
max_size = max(index, max_size);
}
row_count = max_size;
}
time++;
}
}
|
cs |
'BAEKJOON ONLINE JUDGE' 카테고리의 다른 글
[백준 2206] 벽 부수고 이동하기 (C++) (0) | 2021.08.16 |
---|---|
[백준 17135] 캐슬 디펜스 (C++) (0) | 2021.08.16 |
[백준 12100] 2048 (Easy) (C++) (0) | 2021.08.12 |
[백준 20058] 마법사 상어와 파이어스톰 (C++) (0) | 2021.08.11 |
[백준 16235] 나무 재테크 (C++) (0) | 2021.08.10 |