https://www.acmicpc.net/problem/17140

침착하게 따라가면 풀 수 있는 문제이다.

문제 설명 및 입출력

문제에서 추출할 수 있는 정보는 다음과 같다.

• r과 c의 대소관계에 따라 두가지 형태의 연산을 진행한다.
• 행 기준으로, 한 행에 있는 수를 정렬하는 방식은 {수1, 수1의 등장횟수, 수2, 수2의 등장횟수, ...}이며, 은 각각의 수들의 등장 횟수를 카운트한 뒤 등장 횟수의 오름차순으로 정렬하며, 횟수가 같다면 해당 수의 오름차순으로 정렬한다.
• 가장 큰 행을 기준으로 모든 행의 크기가 변한다. 커진 곳에는 0을 채우며, 수를 정렬할 때 0을 무시한다.
• 100을 넘어갈 경우 100개를 제외한 나머지는 버린다.
• A[r][c] = k가 되기 위한 최소 시간을 출력하되, 100초가 지나면 -1을 출력한다.

해결 과정

행/열 연산이 거의 유사하기 때문에, 행 연산 기준으로 다뤄보자.
각 행마다 존재하는 숫자들(0 제외)을 숫자-등장횟수의 형태로 저장해두어야 하므로 map을 사용하였다. 이후 map을 vector로 바꾸고 위 언급한 조건에 따라 정렬한다.

bool cmp(pair<int, int> p1, pair<int, int> p2){
    if(p1.second == p2.second) return p1.first < p2.first;
    return p1.second < p2.second;
}

void R(){ // 행 연산
    for(int i=1; i<=r; i++){
        map<int, int> m; // 숫자-등장횟수
        for(int j=1; j<=c; j++){
            if(arr[i][j] != 0)
                m[arr[i][j]]++;
        }
        vector<pair<int, int> > tmp(m.begin(), m.end());
        sort(tmp.begin(), tmp.end(), cmp);

        int s = 2 * tmp.size(); // 행의 크기 갱신 시도
        c = max(c, s);

        for(int j=1; j<=100; j++) // 0 채우기
            arr[i][j] = 0;
        
        for(int j=0; j<tmp.size(); j++){ // 결과 반영
            arr[i][j*2 + 1] = tmp[j].first;
            arr[i][(j+1)*2] = tmp[j].second;
        }
    }
}

가장 큰 행을 기준으로 모든 행의 크기가 변하기에, c값은 행 연산 시 증가하는 쪽으로 갱신된다. 큰 행이란 r이 아닌 c가 커진다는 것을 의미하기 때문이다. 즉 한 행이 오른쪽으로 길어지는 건 배열 상에서 c가 증가한다는 것이다.

매 행마다 0으로 채워지는 부분을 섬세하게 찾기 번거롭기 때문에, 특정 행을 새로운 연산으로 갱신하기 전 미리 0으로 채워두고, 연산의 결과를 반영한다.

    int t = 0;
    while(1){
        t++;
        if(r >= c){
            R();
        } else {
            C();
        }
        if(arr[tr][tc] == k) break; // 성공
        if(t >= 100){ // 100초가 지남
            cout << -1;
            return 0;
        }
    }
    cout << t;

남은 조건을 반영하여, while문을 통해 시간을 카운트하면서 연산을 진행하면 된다.

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>

using namespace std;
int tr, tc, k;
int r, c;
int arr[101][101];

bool cmp(pair<int, int> p1, pair<int, int> p2){
    if(p1.second == p2.second) return p1.first < p2.first;
    return p1.second < p2.second;
}

void R(){ // 행 연산
    for(int i=1; i<=r; i++){
        map<int, int> m; // 숫자-등장횟수
        for(int j=1; j<=c; j++){
            if(arr[i][j] != 0)
                m[arr[i][j]]++;
        }
        vector<pair<int, int> > tmp(m.begin(), m.end());
        sort(tmp.begin(), tmp.end(), cmp);

        int s = 2 * tmp.size(); // 행의 길이 갱신 시도
        c = max(c, s);

        for(int j=1; j<=100; j++) // 0 채우기
            arr[i][j] = 0;
        
        for(int j=0; j<tmp.size(); j++){ // 결과 반영
            arr[i][j*2 + 1] = tmp[j].first;
            arr[i][(j+1)*2] = tmp[j].second;
        }
    }
}

void C(){ // 열 연산
    for(int i=1; i<=c; i++){
        map<int, int> m;
        for(int j=1; j<=r; j++){
            if(arr[j][i] != 0)
                m[arr[j][i]]++;
        }
        vector<pair<int, int> > tmp(m.begin(), m.end());
        sort(tmp.begin(), tmp.end(), cmp);

        int s = 2 * tmp.size();
        r = max(r, s);
        
        for(int j=1; j<=100; j++)
            arr[j][i] = 0;
        
        for(int j=0; j<tmp.size(); j++){
            arr[j*2 + 1][i] = tmp[j].first;
            arr[(j+1) * 2][i] = tmp[j].second;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0); 
    memset(arr, 0, sizeof(arr));
    cin >> tr >> tc >> k;
    r = 3;
    c = 3;
    for(int i=1; i<=r; i++){
        for(int j=1; j<=c; j++){
            cin >> arr[i][j];
        }
    }

    if(arr[tr][tc] == k){ // 연산 진행할 필요없음
        cout << 0;
        return 0;
    }

    int t = 0;
    while(1){
        t++;
        if(r >= c){
            R();
        } else {
            C();
        }
        if(arr[tr][tc] == k) break; // 성공
        if(t >= 100){ // 100초가 지남
            cout << -1;
            return 0;
        }
    }
    cout << t;
    return 0;
}

교훈

• 빼먹지 않게 조건을 잘 정리하자.