https://www.acmicpc.net/problem/17140
17140번: 이차원 배열과 연산
첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.
www.acmicpc.net
행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.
일단 배열의 크기는 넉넉하게 105정도로 잡자.
배열의 인덱스는 1부터 시작해야지 정답을 낼 수 있다.
변수에 time은 못쓴다. time 이란 단어가 이미 존재
jikan이라고 쓰자
계속 돌려야 하니까 while(true)
if 문으로 R 연산 할지 C 연산 할지 정하자.
행의 개수 ≥ 열의 개수
행의 개수 < 열의 개수
1부터 100까지 정수만 들어가니까
한 줄 당 1부터 100까지 for문 돌려서 num_cnt 배열을 초기화
행 또는 열의 크기가 커진 곳에는 0이 채워진다.
수를 정렬할 때 0은 무시해야 한다.
예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.
벡터를 만들어서 벡터에 저장하자.
vector<pair<int, int>> han;
정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.
vector<pair<int,int>> 써서 수와 등장횟수를 배열에 넣어주면 되겠다.
sort에 cmp를 안써도 조건에 맞게 정렬이 가능하다.
일단 한 줄을 0으로 크기만큼 채우고
index = 1부터 정렬 한 값들로 바꿔준다.
|
1
2
3
4
5
6
7
8
9
|
int index = 1;
for (int x = 0; x < han.size(); x++)
{
map[i][index] = han[x].second;
index++;
map[i][index] = han[x].first;
index++;
}
index--;
|
cs |
정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다
index들을 kugi 벡터에 넣어서
sort를 하고 마지막 값을 hang이나 yul로 바꿔준다.
<소스 코드>
|
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
|
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int map[105][105];
int num_cnt[105];
int r, c, k;
int ans = 987654321;
void solve()
{
int hang = 3;
int yul = 3;
int jikan = 0;
while (true)
{
if (map[r][c] == k)
{
ans = jikan;
break;
}
if (jikan > 100)
{
ans = -1;
break;
}
vector<int> kugi;
if (hang >= yul)
{
for (int i = 1; i <= hang; i++)
{
vector<pair<int, int>> han;
memset(num_cnt, 0, sizeof(num_cnt));
for (int j = 1; j <= yul; j++)
num_cnt[map[i][j]]++;
for (int n = 1; n <= 100; n++)
{
if (num_cnt[n] == 0)
continue;
han.push_back({ num_cnt[n], n });
}
sort(han.begin(), han.end());
for (int j = 1; j <= yul; j++)
map[i][j] = 0;
int index = 1;
for (int x = 0; x < han.size(); x++)
{
map[i][index] = han[x].second;
index++;
map[i][index] = han[x].first;
index++;
}
index--;
kugi.push_back(index);
}
sort(kugi.begin(), kugi.end());
yul = kugi.back();
}
else if (hang < yul)
{
for (int j = 1; j <= yul; j++)
{
vector<pair<int, int>> han;
memset(num_cnt, 0, sizeof(num_cnt));
for (int i = 1; i <= hang; i++)
num_cnt[map[i][j]]++;
for (int n = 1; n <= 100; n++)
{
if (num_cnt[n] == 0)
continue;
han.push_back({ num_cnt[n], n });
}
sort(han.begin(), han.end());
for (int i = 1; i <= hang; i++)
map[i][j] = 0;
int index = 1;
for (int x = 0; x < han.size(); x++)
{
map[index][j] = han[x].second;
index++;
map[index][j] = han[x].first;
index++;
}
index--;
kugi.push_back(index);
}
sort(kugi.begin(), kugi.end());
hang = kugi.back();
}
jikan++;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> r >> c >> k;
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
cin >> map[i][j];
}
if (map[r][c] == k)
cout << 0 << '\n';
else
{
solve();
cout << ans << '\n';
}
return 0;
}
|
cs |
