반응형
17140번 이차원 배열과 연산
1. 이해하기
- 처음은 크기가 3x3인 배열로 시작한다.
- 1초가 지날때마다 배열에 연산이 적용된다.
- R 연산: 배열의 모든 행에 대해서 정렬을 수행한다. 행의 개수 >= 열의 개수인 경우에 적용된다.
- C 연산: 배열의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.
- 정렬하는 방법은 다음과 같다.
- 각각의 수가 몇 번 나왔는지 센다.
- 수의 등장 횟수가 커지는 순으로, 이것이 여러가지면 수가 커지는 순으로 정렬한다.
- 배열에 정렬된 결과를 다시 넣어준다.
- 넣어줄때 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.
- 행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.
- (r,c)에 들어있는 값이 k가 되기 위한 최소 시간을 구하는 문제.
- 시뮬레이션 문제이다.
2. 구현하기
-
R 연산과 C 연산을 각각 구현한다.
- 이때, 배열에 들어있는 값은 100이 넘을 수 없으므로 크기 100을 가지는 배열을 이용한다.
- 바로 원래 배열에 적용하면 배열의 크기가 줄어들었을 때 제대로 처리를 못하는 경우가 나오니 임시 배열에 바뀐 값을 적용하고 과정이 끝나면 원래 배열에 임시 배열 값을 옮긴다.
void R(int row_cnt, int& col_cnt) { int next_col_cnt = 0; memset(temp_map,0,sizeof(temp_map)); for(int i = 0; i < row_cnt; i++) { memset(temp_row,0,sizeof(temp_row)); for(int j = 0; j < col_cnt; j++) { if(map[i][j] == 0) continue; int now = map[i][j]; temp_row[now].num = now; temp_row[now].cnt++; } sort(temp_row,temp_row+101); int index = 0; for(int j = 1; j <= 100; j++) { if(temp_row[j].cnt == 0) continue; if(index >= 100) break; temp_map[i][index] = temp_row[j].num; temp_map[i][index+1] = temp_row[j].cnt; index+=2; } next_col_cnt = max(next_col_cnt,index); } col_cnt = next_col_cnt; copy_temp_to_map(row_cnt, col_cnt); } void C(int& row_cnt, int col_cnt) { int next_row_cnt = 0; memset(temp_map,0,sizeof(temp_map)); for(int i = 0; i < col_cnt; i++) { memset(temp_col,0,sizeof(temp_col)); for(int j = 0; j < row_cnt; j++) { if(map[j][i] == 0) continue;; int now = map[j][i]; temp_col[now].num = now; temp_col[now].cnt++; } sort(temp_col,temp_col+101); int index = 0; for(int j = 1; j <= 100; j++) { if(temp_col[j].cnt == 0) continue; if(index >= 100) break; temp_map[index][i] = temp_col[j].num; temp_map[index+1][i] = temp_col[j].cnt; index+=2; } next_row_cnt = max(next_row_cnt,index); } row_cnt = next_row_cnt; copy_temp_to_map(row_cnt,col_cnt); }
-
초기 배열의 크기를 3x3로 설정하고 (r,c)의 값이 k가 될때까지 반복한다. 이때, 100초가 넘어가면 -1을 반환한다.
int simulate() { int ret = 0; int row_cnt = 3, col_cnt = 3; while(1) { if(map[r][c] == k) break; if(ret > 100) return -1; if(row_cnt >= col_cnt) { R(row_cnt,col_cnt); } else { C(row_cnt,col_cnt); } ret++; } return ret; }
3. 전체 코드
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct INF {
int num,cnt;
bool operator<(INF inf) const{
if(cnt == inf.cnt) return num < inf.num;
else return cnt < inf.cnt;
}
};
int map[100][100], temp_map[100][100];
INF temp_row[101], temp_col[101];
int r,c,k;
void copy_temp_to_map(int row_cnt, int col_cnt) {
for(int i = 0; i < row_cnt; i++) {
for(int j = 0; j < col_cnt; j++) {
map[i][j] = temp_map[i][j];
}
}
}
void R(int row_cnt, int& col_cnt) {
int next_col_cnt = 0;
memset(temp_map,0,sizeof(temp_map));
for(int i = 0; i < row_cnt; i++) {
memset(temp_row,0,sizeof(temp_row));
for(int j = 0; j < col_cnt; j++) {
if(map[i][j] == 0) continue;
int now = map[i][j];
temp_row[now].num = now;
temp_row[now].cnt++;
}
sort(temp_row,temp_row+101);
int index = 0;
for(int j = 1; j <= 100; j++) {
if(temp_row[j].cnt == 0) continue;
if(index >= 100) break;
temp_map[i][index] = temp_row[j].num;
temp_map[i][index+1] = temp_row[j].cnt;
index+=2;
}
next_col_cnt = max(next_col_cnt,index);
}
col_cnt = next_col_cnt;
copy_temp_to_map(row_cnt, col_cnt);
}
void C(int& row_cnt, int col_cnt) {
int next_row_cnt = 0;
memset(temp_map,0,sizeof(temp_map));
for(int i = 0; i < col_cnt; i++) {
memset(temp_col,0,sizeof(temp_col));
for(int j = 0; j < row_cnt; j++) {
if(map[j][i] == 0) continue;;
int now = map[j][i];
temp_col[now].num = now;
temp_col[now].cnt++;
}
sort(temp_col,temp_col+101);
int index = 0;
for(int j = 1; j <= 100; j++) {
if(temp_col[j].cnt == 0) continue;
if(index >= 100) break;
temp_map[index][i] = temp_col[j].num;
temp_map[index+1][i] = temp_col[j].cnt;
index+=2;
}
next_row_cnt = max(next_row_cnt,index);
}
row_cnt = next_row_cnt;
copy_temp_to_map(row_cnt,col_cnt);
}
int simulate() {
int ret = 0;
int row_cnt = 3, col_cnt = 3;
while(1) {
if(map[r][c] == k) break;
if(ret > 100) return -1;
if(row_cnt >= col_cnt) {
R(row_cnt,col_cnt);
} else {
C(row_cnt,col_cnt);
}
ret++;
}
return ret;
}
void input() {
cin >> r >> c >> k;
r--; c--;
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
cin >> map[i][j];
}
}
}
int main() {
input();
cout << simulate() << '\n';
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 17822번 원판 돌리기 (0) | 2019.10.24 |
---|---|
[백준] 17142번 연구소 3 (0) | 2019.10.14 |
[백준] 17143번 낚시왕 (0) | 2019.10.11 |
[백준] 17144번 미세먼지 안녕! (0) | 2019.10.11 |
[백준] 16236번 아기 상어 (0) | 2019.10.10 |