백준 17140번 - 이차원 배열과 연산

www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

난이도 자체는 어렵지 않았으나 구현이 너무 복잡했다..

 

처음에 map으로 접근해보려다가 2시간 넘게 날리고 다시 그냥 배열로 접근했다..

(처음부터 배열로 접근할걸 괜히 까불다가)

 

이 문제의 핵심 포인트는 아무래도 매 연산마다 바뀌는 숫자들의 개수를 파악해놓는 것 아닐까 싶다.

 

그리고 이런 문제를 풀때마다 실수하는 점은 i와 j를 헷갈리거나 +=인데 -=으로 쓰는 등 이런 점들을 조심해야 한다

(내가 저것들 땜에 1시간은 버렸다ㅠ)

 

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef pair<int, int> pii;
int arr[107][107];
int rm[107][107];
int cm[107][107];
 
int main() {
    int r, c, k, x;
    int row = 3, col = 3;
    cin >> r >> c >> k;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> x;
            arr[i][j] = x;
            rm[i][x] += 1;
            cm[j][x] += 1;
        }
    }
    int ans = 0;
    while (1) {
        if (ans > 100 || arr[r - 1][c - 1] == k)break;
        ans += 1;
        if (row >= col) { // R 연산 시행
            int max_size = 0;
            for (int i = 0; i < row; i++) { // 모든 행에 대하여 연산
                vector<pii>temp;
                for (int j = 1; j <= 100; j++) {
                    if (rm[i][j] > 0) temp.push_back(pii(rm[i][j], j));
                    rm[i][j] = 0;
                }
                sort(temp.begin(), temp.end()); // 정렬
                int size = temp.size();
                max_size = max(size * 2, max_size);
                int cnt = 0;
                for (int j = 0; j < 50; j++) {
                    cm[cnt][arr[i][cnt]] -= 1; cm[cnt + 1][arr[i][cnt + 1]] -= 1;
                    if (j >= size) {
                        arr[i][cnt] = 0; arr[i][cnt + 1] = 0;
                    }
                    else {
                        rm[i][temp[j].first] += 1; rm[i][temp[j].second] += 1;
                        arr[i][cnt] = temp[j].second; arr[i][cnt + 1] = temp[j].first;
                        cm[cnt][temp[j].second] += 1; cm[cnt + 1][temp[j].first] += 1;
                    }
                    cnt += 2;
                }
            }
            col = max(max_size, col);
        }
        else {
            int max_size = 0;
            for (int i = 0; i < col; i++) { // 모든 열에 대하여 연산
                vector<pii>temp;
                for (int j = 1; j <= 100; j++) {
                    if (cm[i][j] > 0) temp.push_back(pii(cm[i][j], j));
                    cm[i][j] = 0;
                }
                sort(temp.begin(), temp.end()); // 정렬
                int size = temp.size();
                max_size = max(size * 2, max_size);
                int cnt = 0;
                for (int j = 0; j < 50; j++) {
                    rm[cnt][arr[cnt][i]] -= 1; rm[cnt + 1][arr[cnt + 1][i]] -= 1;
                    if (j >= size) {
                        arr[cnt][i] = 0; arr[cnt + 1][i] = 0;
                    }
                    else {
                        cm[i][temp[j].first] += 1; cm[i][temp[j].second] += 1;
                        arr[cnt][i] = temp[j].second; arr[cnt + 1][i] = temp[j].first;
                        rm[cnt][temp[j].second] += 1; rm[cnt + 1][temp[j].first] += 1;
                    }
                    cnt += 2;
                }
            }
            row = max(max_size, row);
        }
    }
    if (arr[r - 1][c - 1] == k) cout << ans << "\n";
    else cout << "-1" << "\n";
}

 

코드가 길어서 이해하기 어렵지만..

여러 생각들이 겹치다 보니 너무 복잡하게 구현된 것 같다...