-
[BOJ] 17140번 이차원 배열과 연산알고리즘/BOJ 2020. 7. 31. 19:14
https://www.acmicpc.net/problem/17140
아이디어
1, 행 정렬과 열 정렬을 함수를 구분하여 동작하게 해 준다.
2, 행 혹은 열을 정렬할 때 각각의 숫자와 등장 횟수를 담는 구조체를 선언을 한 다음 벡터에 저장을 해 준다.
3, compare함수를 통하여 문제의 조건인 "등장 횟수가 커지는 식으로, 그 수가 같다면 수가 커지는 순으로" 벡터에 있는 구조체를 정렬한다.
4, 행 혹은 열을 위와 같은 방식으로 연산을 진행하고 문제의 조건에 맞게 답을 출력한다.
#include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; int arr[101][101]; typedef struct info { int num; int cnt; }info; int row_cnt, col_cnt; int num_cnt[101]; int r, c, k; bool compare(info a, info b) { if (a.cnt < b.cnt) { return true; } else if (a.cnt > b.cnt) { return false; } else { if (a.num < b.num) { return true; } else { return false; } } } vector<info> num_count() { info insert; vector<info> res; for (int j = 1; j < 101; j++) { if (num_cnt[j] != 0) { insert.num = j; insert.cnt = num_cnt[j]; res.push_back(insert); } } return res; } void row_calc() { //행에 대하여 정렬 vector<info> renewal; vector<info>::iterator iter; vector<int> renewal2; int max_len = 0; for (int i = 0; i < row_cnt; i++) { memset(num_cnt, 0, sizeof(num_cnt)); renewal.clear(); renewal2.clear(); for (int j = 0; j < col_cnt; j++) { num_cnt[arr[i][j]]++; } renewal = num_count(); sort(renewal.begin(), renewal.end(), compare); for (iter = renewal.begin(); iter != renewal.end(); iter++) { renewal2.push_back(iter->num); renewal2.push_back(iter->cnt); } for (int j = 0; j < col_cnt; j++) { arr[i][j] = 0; } int renewal2_size = renewal2.size(); for (int j = 0; j < renewal2_size; j++) { if (j == 100) break; arr[i][j] = renewal2[j]; } if (max_len < renewal2.size()) max_len = renewal2_size; } if (max_len > 100) max_len = 100; col_cnt = max_len; } void col_calc() { //열에 대하여 정렬 vector<info> renewal; vector<info>::iterator iter; vector<int> renewal2; info insert; int max_len = 0; for (int i = 0; i < col_cnt; i++) { memset(num_cnt, 0, sizeof(num_cnt)); renewal.clear(); renewal2.clear(); for (int j = 0; j < row_cnt; j++) { num_cnt[arr[j][i]]++; } renewal = num_count(); sort(renewal.begin(), renewal.end(), compare); for (iter = renewal.begin(); iter != renewal.end(); iter++) { renewal2.push_back(iter->num); renewal2.push_back(iter->cnt); } for (int j = 0; j < row_cnt; j++) { arr[j][i] = 0; } int renewal2_size = renewal2.size(); for (int j = 0; j < renewal2_size; j++) { if (j == 100) break; arr[j][i] = renewal2[j]; } if (max_len < renewal2.size()) max_len = renewal2_size; } if (max_len > 100) max_len = 100; row_cnt = max_len; } int main() { int temp; vector<int> insert; int res = 0; scanf("%d %d %d", &r, &c, &k); for (int i = 0; i < 3; i++) { insert.clear(); for (int j = 0; j < 3; j++) { scanf("%d", &temp); arr[i][j] = temp; } } row_cnt = 3; col_cnt = 3; while (1) { if (res > 100) break; if (arr[r - 1][c - 1] == k) { break; } if (row_cnt >= col_cnt) row_calc(); else col_calc(); res++; } if (res == 101) { printf("%d\n", -1); } else { printf("%d\n", res); } return 0; }
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ]16234번 인구 이동 (0) 2020.08.14 [BOJ] 17837번 새로운 게임2 (0) 2020.08.04 [BOJ] 15684번 사다리 조작 (0) 2020.07.31 [BOJ] 15683번 감시 (0) 2020.07.30 [BOJ] 14891번 톱니바퀴 (0) 2020.07.30