문제 URL : https://www.acmicpc.net/problem/17140
17140번: 이차원 배열과 연산
첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.
www.acmicpc.net
문제 접근법 :
r연산 c연산을 하기전에 문제를 정확히 이해하시는게 중요합니다.
문제가 이해가안되서 여러번 읽게됐는데
3,1,1 이있다면 3이 1개 1이 2개니까
이걸 묶어서 (3,1),(1,2) 이런식으로 새로운 배열이 탄생합니다.
만약 1,2,3 이었다면 (1,1),(2,1),(3,1) 각각 한개씩 있으므로
1,1,2,1,3,1 이런식으로 만들어진다는 걸 알아야합니다.
즉이것을 2차원 배열로 적용하면
백준문제집에 있는
힌트를 확인하면
1 2 1
2 1 3
3 3 3
가장 처음에는 행의 개수 ≥ 열의 개수 이기 때문에, R 연산이 적용된다. 편의상 정렬 중간 단계는 (수, 수의 등장 횟수)로 표현한다.
1 2 1 → (2, 1), (1, 2) → 2 1 1 2
2 1 3 → (1, 1), (2, 1), (3, 1) → 1 1 2 1 3 1
3 3 3 → (3, 3) → 3 3크기가 가장 큰 행은 2번 행이고, 나머지 행의 뒤에 0을 붙여야 한다.
2 1 1 2 0 0
1 1 2 1 3 1
3 3 0 0 0 0다음에 적용되는 연산은 행의 개수 < 열의 개수이기 때문에 C 연산이다.
1 3 1 1 3 1
1 1 1 1 1 1
2 1 2 2 0 0
1 2 1 1 0 0
3 0 0 0 0 0
1 0 0 0 0 0이런식의 배열이 만들어질때 행의개수와 열의수만 확인해서 행기준 혹은 열기준으로 바꿔서 그대로 구현하면 되는문제입니다.
소스코드 :
|
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
|
#include<bits/stdc++.h>
using namespace std;
#define v vector
#define vi v<int>
#define vvi v<vi>
#define p pair<int,int>
int r, c, k;
vvi board(3,vi(3));
void input() {
cin >> r >> c >> k;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cin >> board[i][j];
}
}
r--, c--;
}
void solve() {
int res = 0;
while (true) {
if (r < board.size() && c < board[0].size() && board[r][c] == k)
break;
res++;
if (res > 100) {
cout << -1 << "\n";
return;
}
if (board.size() >= board[0].size()) {
int maxsize = 0;
for (int i = 0; i < board.size(); i++) {
unordered_map<int, int> m;
priority_queue<p, v<p>, greater<p>> pq;
vi t;
for (int j = 0; j < board[i].size(); j++) {
if (board[i][j] == 0)continue;
m[board[i][j]]++;
}
for (auto it : m)pq.push({ it.second,it.first });
while (!pq.empty()) {
t.push_back(pq.top().second);
t.push_back(pq.top().first);
pq.pop();
}
while (t.size() > 100)
t.pop_back();
maxsize = max(maxsize, (int)t.size());
board[i] = t;
}
for (int i = 0; i < board.size(); i++) {
for (; board[i].size() < maxsize;)
board[i].push_back(0);
}
}
else {
int maxsize = 0;
vvi temp;
for (int j = 0; j < board[0].size(); j++) {
unordered_map<int, int> m;
priority_queue<p, v<p>, greater<p>> pq;
vi t;
for (int i = 0; i < board.size(); i++) {
if (board[i][j] == 0)continue;
m[board[i][j]]++;
}
for (auto it : m)pq.push({ it.second,it.first });
while (!pq.empty()) {
t.push_back(pq.top().second);
t.push_back(pq.top().first);
pq.pop();
}
while (t.size() > 100)
t.pop_back();
temp.push_back(t);
maxsize = max(maxsize, (int)t.size());
}
for (int i = 0; i < temp.size(); i++) {
for (; temp[i].size() < maxsize;)
temp[i].push_back(0);
}
board.clear();
for (int j = 0; j < temp[0].size(); j++) {
vi t;
for (int i = 0; i < temp.size(); i++)
t.push_back(temp[i][j]);
board.push_back(t);
}
}
}
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 20005 보스몬스터 전리품 (0) | 2022.03.30 |
|---|---|
| 백준 9328 열쇠 (0) | 2022.03.29 |
| 백준 2638 치즈 (0) | 2022.03.29 |
| 백준 6198 옥상 정원 꾸미기 (0) | 2022.03.22 |
| 백준 16724 피리 부는 사나이 (0) | 2022.03.22 |
