Algorithm/구현(Brute force, Back tracking, etc.)
백준 17140 이차원 배열과 연산
쩡류
2021. 3. 4. 17:11
728x90
while문을 통해 answer<= 100인 조건 적용하고,
만약 문제에 주어진 arr[r][c] == k 조건을 만족하면 break 하도록 조건 걸어준다.
while문 내부에서는
1. 행의 갯수 >= 열의 갯수 시 'r연산' 적용
0. 가장 먼저, vector<int> 벡터를 만든다.(한 개의 행마다 진행할 것임)
1. for문 통해 해당 행에 있는 숫자 갯수 조사 후(index 사용) pair쌍을 벡터에 push_back
2. 내가 정해둔 기준에 따라 벡터를 정렬한다. (second 먼저 비교하고 그 다음 first 순으로 오름차순 정렬)
3. 벡터를 for문으로 돌리면서 arr를 최신화. 이 때 size 비교하면서 max 조사한다. max * 2가 결국 다음 col 값이 된다.
4. index 초기화 후 다음 행 진행
5. 만약 모든 행 연산 완료시 col 최신화
2. else 'c연산' 적용
0. 가장 먼저, vector<int> 벡터를 만든다.(한 개의 열마다 진행할 것임)
1. for문 통해 해당 열에 있는 숫자 갯수 조사 후(index 사용) pair쌍을 벡터에 push_back
2. 내가 정해둔 기준에 따라 벡터를 정렬한다.
3. 벡터를 for문으로 돌리면서 arr를 최신화. 이 때 size 비교하면서 max 조사한다. max * 2가 결국 다음 col 값이 된다.
4. index 초기화 후 다음 행 진행
5. 만약 모든 행 연산 완료시 col 최신화
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define MAX 101
using namespace std;
int arr[MAX][MAX]; //
int num_index[101];
bool compare(pair<int, int> a, pair<int, int> b) {
if (a.second == b.second)
return a.first < b.first;
else return a.second < b.second;
}
int main() {
int r, c, k;
cin >> r >> c >> k;
int num_row = 3;
int num_col = 3;
for (int i = 0; i < num_row; i++) {
for (int j = 0; j < num_col; j++) {
cin >> arr[i][j];
}
}
int answer = 0;
while (answer <= 100) {
if (r-1 < num_row && c-1 < num_col && arr[r-1][c-1] == k) break;
if (num_row >= num_col) { // r연산
int max_length_of_col = num_col;
for (int i = 0; i < num_row; i++) {
int temp_max = 0; // 배열 내부 값 중 가장 큰 값을 저장.
for (int j = 0; j < num_col; j++) {
if (!arr[i][j]) continue;
num_index[arr[i][j]]++;
temp_max = max(temp_max, arr[i][j]);
}
vector<pair<int,int>> temp_v2;
for (int j = 1; j <= temp_max; j++) {
if (num_index[j] != 0) temp_v2.push_back({ j,num_index[j] });
}
sort(temp_v2.begin(), temp_v2.end(), compare);
max_length_of_col = max(max_length_of_col, int(temp_v2.size() * 2));
for (int j = 0; j < temp_v2.size(); j++) {
arr[i][j * 2] = temp_v2[j].first;
arr[i][j * 2 + 1] = temp_v2[j].second;
}
for (int j = temp_v2.size()*2; j < num_col; j++) arr[i][j] = 0;
memset(num_index, 0, sizeof(num_index));
}
num_col = max_length_of_col;
}
else { // c연산
int max_length_of_row = num_row;
for (int i = 0; i < num_col; i++) {
int temp_max = 0; // 배열 내부 값 중 가장 큰 값을 저장.
for (int j = 0; j < num_row; j++) {
if (!arr[j][i]) continue;
num_index[arr[j][i]]++;
temp_max = max(temp_max, arr[j][i]);
}
vector<pair<int, int>> temp_v2;
for (int j = 1; j <= temp_max; j++) {
if (num_index[j] != 0) temp_v2.push_back({ j,num_index[j] });
}
sort(temp_v2.begin(), temp_v2.end(), compare);
max_length_of_row = max(max_length_of_row, int(temp_v2.size() * 2));
for (int j = 0; j < temp_v2.size(); j++) {
arr[j*2][i] = temp_v2[j].first;
arr[j*2+1][i] = temp_v2[j].second;
}
for (int j = temp_v2.size()*2; j < num_row; j++) arr[j][i] = 0;
memset(num_index, 0, sizeof(num_index));
}
num_row = max_length_of_row;
}
answer++;
}
if (answer > 100) answer = -1;
cout << answer << '\n';
return 0;
}