https://www.acmicpc.net/problem/17140
17140번: 이차원 배열과 연산
첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.
www.acmicpc.net
문제를 처음 접했을 때 쉬워 보이는데 조건이 왜이리 많아 생각이 드는 문제네요.
간단히 어떤식으로 코딩을 해야할지 틀을 잡아보겠습니다.
우선 R 연산과 C연산으로 조건이 갈립니다.
R연산은 행의 개수 >= 열의 개수 인 경우 적용되는데
그림으로 보시면 이해가빠르겠죠?
아래 그림을 보시면
행과 열이 같거나
행이 열보다 크면 R연산을 진행하는것입니다.
C 연산의 경우
열이 행보다 많은 경우 C연산을 진행합니다.
여기까지는 이해가 쉽고 가장 중요한것은
3 2 2 인경우를 예로 들면 3은 1개 2는 2개 있다면
1. 다음 수의 등장 횟수가 커지는 순
즉, 위의 경우에는 3은 1개 2는 2개이므로 등장횟수가 점점 커지는 순으로 3 1 2 2 가되고
만약에
3 1 2 인경우를 예로 들면 3은 1개 2는 1개 1은 1개가 나왔는데
2. 그러한 것이 여러가지면 수가 커지는 순으로 정렬
즉, 위의 경우와 같이 같은 갯수로 나왔다면 숫자가 커지는 순으로 오름차순 정렬
1 1 2 1 3 1 로 정렬해라는 말입니다.
그렇게 R연산인지 C연산인지를 판별을 하면서 배열에 입력하고
만약에 행 또는 열의 크기가 100을 넘어간다면 100을 유지하도록 해주고
100번의 반복동안 첫줄에 주어지는 r c k
배열 A를 돌린다 생각하시고 배열의 A[r][c]==k 이면 그 반복횟수 만큼 출력을 하고 100번동안 나오지 않는다면
-1을 출력하면 이상입니다.
여기서 포인트
조건 1,2가 되도록 현재 1부터 100까지의 숫자가 몇개 있는지 어디에 저장하는지가 문제인데
구조체 배열을 선언하여 구조체에는 멤버로 숫자의 번호 , 몇번나왔는지 저장할수있는 num과 cnt를 주고
구조체배열 [101];을 선언하시면됩니다.
아래 소스를 보면서 분석해보세요.
|
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
|
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
int r, c, k;
int map[101][101];
int chk_num[101];
struct sort_num
{
int num; int cnt;
};
bool compare(const sort_num&a, const sort_num&b) {
return a.num > b.num;
}
bool compare1(const sort_num&a, const sort_num&b) {
if (a.cnt == b.cnt)return a.num < b.num;
else return a.cnt < b.cnt;
}
int main(void) {
scanf("%d %d %d", &r, &c, &k);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
scanf("%d", &map[i][j]);
}
}
int year = 101;
int cy=3, cx=3;
while (year--) {
if (cy >= 100)cy = 99;
if (cx >= 100)cx = 99;
if (map[r-1][c-1] == k) {
printf("%d\n", 100 - year);
return 0;
}
int idx = 0;
int max_idx = 0x80000000;
int iidx = 0;
if (cy >= cx) {//R연산
for (int i = 0; i < cy;i++) {
idx = -987654321;
iidx = 0;
sort_num SN[101] = { 0,0 };
memset(chk_num, 0, sizeof(chk_num));
for (int j = 0; j < cx; j++) {
if (map[i][j] == 0)continue;
if (idx < map[i][j]) idx = map[i][j];
if (chk_num[map[i][j]] == 0) {
chk_num[map[i][j]] = 1;
iidx++;
}
SN[map[i][j]].num = map[i][j];
SN[map[i][j]].cnt++;
map[i][j] = 0;
}
sort(SN, SN+idx+1,compare);
sort(SN, SN+iidx,compare1);
if (iidx >= 100)iidx = 100;
idx = 0;
for (int x = 0; x < iidx; x++) {
map[i][idx] = SN[x].num;
map[i][++idx] = SN[x].cnt;
++idx;
}
if (max_idx < iidx*2) max_idx = iidx*2;
}
cx = max_idx;
}
else if (cy < cx) {//C 연산
max_idx = 0x80000000;
for (int j = 0; j < cx; j++) {
idx = -987654321;
iidx = 0;
sort_num SN[101] = { 0,0 };
memset(chk_num, 0, sizeof(chk_num));
for (int i = 0; i < cy; i++) {
if (map[i][j] == 0)continue;
if (idx < map[i][j]) idx = map[i][j];
if (chk_num[map[i][j]] == 0) {
chk_num[map[i][j]] = 1;
iidx++;
}
SN[map[i][j]].num = map[i][j];
SN[map[i][j]].cnt++;
map[i][j] = 0;
}
sort(SN, SN+idx+1,compare);
sort(SN, SN+iidx,compare1);
if (iidx >= 100)iidx = 100;
idx = 0;
for (int y = 0; y < iidx; y++) {
map[idx][j] = SN[y].num;
map[++idx][j] = SN[y].cnt;
++idx;
}
if (max_idx < iidx * 2) max_idx = iidx * 2;
}
cy = max_idx;
}
}
printf("-1");
return 0;
}
|
sort함수는 헤더파일 #include<algorithm>을 선언하시고
struct sort_num
{
int num; int cnt;
}SN[101];
bool compare(const sort_num&a, const sort_num&b) {
return a.num > b.num; // 내림차순
}
bool compare1(const sort_num&a, const sort_num&b) {
return a.num < b.num; // 오름차순
}
sort(SN, SN+iidx,compare);
// sort(구조체배열이름(0번째 부터 할꺼라서 이름만쓰는것입니다.), 구조체배열이름 + 정렬을 원하는 위치인데스값,
비교함수);
구조는 대략 이런식으로 해서 정렬하시면됩니다.
나머지는 단순 구현이라 구현력이 어느정도 되시면 금방하십니다.
여기서 가장 큰 실수 했던것이 처음에 100까지 숫자를 구조체배열에 그자체를 인덱스로 쓰기위해서는 101을 선언해야
하는데 100을 선언해서 런타임에러가 생기더라구요 여러분들은 이런실수 절대 하지 마세요.
구조체배열 정렬하는법도 배워가셔서 많이 사용해 보세요. 사용하면 할수록 자기것이 됩니다.
오늘은 여기까지입니다. 감사합니다.
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 17143 낚시왕 (0) | 2019.07.12 |
|---|---|
| 백준 16939 2×2×2 큐브 (0) | 2019.07.12 |
| 백준 1759 암호만들기 (0) | 2019.07.09 |
| 배열의 선언, 입력, 출력 (정수형 편)- 긴글 주의!!- (0) | 2019.07.07 |
| 백준 2580 스도쿠 (0) | 2019.07.04 |
댓글