[BOJ] 17140 - 이차원 배열과 연산

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

처음에는 R, C만큼만 확인해주다가 답이 나오지 않아 고생했고, 어떻게든 100번을 모두 돌리고 싶지 않아 여러 시도를 해봤지만 반례가 자꾸 나와서 정신건강을 위해 화끈하게 100번을 돌려주었다.

소스코드

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <string.h>
#include <queue>
#include <functional>
using namespace std;
typedef pair<int, int> PII;

int arr[105][105], n, r, c, k;

int main(void) {
    int cnt = 0, R = 3, C = 3;

    scanf("%d %d %d", &r, &c, &k);

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            scanf("%d", arr[i] + j);
        }
    }
    r--; c--;
    if (arr[r][c] == k) {
        printf("0");
        return 0;
    }
    while (cnt++ < 100) {
        if (R >= C) {
            C = 0;
            for (int i = 0; i < 100; i++) {
                priority_queue<PII, vector<PII>, greater<PII>> pq;
                map<int, int> m;
                for (int j = 0; j < 100; j++) {
                    if (arr[i][j] != 0)
                        m[arr[i][j]]++;
                }
                for (auto it = m.begin(); it != m.end(); it++) {
                    pq.push({ it->second, it->first });
                }
                C = max(C, min((int)pq.size() * 2, 100));
                for (int j = 0; j < 100; j+=2) {
                    if(!pq.empty()){
                        arr[i][j] = pq.top().second;
                        arr[i][j + 1] = pq.top().first;
                        pq.pop();
                    }
                    else {
                        arr[i][j] = arr[i][j + 1] = 0;
                    }
                }
            }
        }
        else {
            R = 0;
            for (int i = 0; i < 100; i++) {
                priority_queue<PII, vector<PII>, greater<PII>> pq;
                map<int, int> m;
                for (int j = 0; j < 100; j++) {
                    if (arr[j][i] != 0)
                        m[arr[j][i]]++;
                }
                for (auto it = m.begin(); it != m.end(); it++) {
                    pq.push({ it->second, it->first });
                }
                R = max(R, min((int)pq.size() * 2, 100));
                for (int j = 0; j < 100; j += 2) {
                    if (!pq.empty()) {
                        arr[j][i] = pq.top().second;
                        arr[j + 1][i] = pq.top().first;
                        pq.pop();
                    }
                    else {
                        arr[j][i] = arr[j + 1][i] = 0;
                    }
                }
            }
        }
        if (arr[r][c] == k) {
            printf("%d", cnt);
            return 0;
        }
    }
    printf("-1");
    return 0;
}