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

Table Of Contents

1. 문제 요약

입력으로

r
,
c
,
k
가 주어지고,
{arr[r][c] = k}
가 되려면 연산을 몇 번 수행해야 하는지 구해야 한다.

{1 <= r, c, k <= 100}

초기 배열은 3x3이고, 1초마다 배열에 연산을 한 번씩 적용한다.

여기에서 말하는 정렬 연산은 이렇게 정의된다.

예를 들어서, 1, 1, 3이라는 행이 있다면, 1이 2번, 3이 1번 나왔으므로 3, 1, 1, 2처럼 정렬된다.

2. 풀이 정리

다음과 같은 점들을 보아 100초동안 모든 경우를 탐색하면 될 것 같았다.

R연산과 C연산을 언제 수행하는지가 명확하기 때문에,

{arr[r][c]}
k
가 될 때까지, 또는 100초에 도달할 때까지 정해진 연산을 수행하면 된다.

나는 solve함수에서 연산을 수행했다.

  1. 현재 행의 숫자(
    R
    )과 열의 숫자(
    C
    )를 비교하여 올바른 연산을 수행한다.
    • R 연산의 경우, 모든 행에 대하여, 숫자 갯수를 센다.
    • 그리고 등장 횟수가 0이 아닌 수들을 priority queue에 { 수의 등장 횟수, 수 } pair를 push해준다.
    • pq에서 pair를 하나씩 뽑으면서 tmp 배열을 채워주고, 이 과정에서 정렬 연산이 끝난 후 열의 길이도 구해준다.
    • tmp배열을 arr 배열에 복사하고, 열의 길이를 갱신한다.
    • 만약
      {arr[r][c]} = k
      가 되었다면, 답을 출력한다.
    • C 연산은 행과 열을 바꾸어 수행하면 된다.

3. 구현

나는 배열의 시작을 0으로 잡았기 때문에 r - 1, c - 1등으로 인덱싱했다.

#include <iostream> #include <algorithm> #include <vector> #include <queue> # define endl '\n' #define pii pair<int, int> using namespace std; int r, c, k; int arr[205][205]; int tmp[205][205]; int R = 3, C = 3; bool flag = false; void solve() { priority_queue<pii, vector<pii>, greater<pii> > pq; int nexR = R, nexC = C; if (R >= C) { for (int rr = 0; rr < R; rr++) { int count[105] = { 0, }; for (int cc = 0; cc < C; cc++) { count[arr[rr][cc]]++; } for (int i = 1; i <= 100; i++) { if (count[i]) pq.push({ count[i], i }); } for (int i = 0; i < 100; i++) { if (!pq.empty()) { tmp[rr][i * 2] = pq.top().second; tmp[rr][i * 2 + 1] = pq.top().first; pq.pop(); nexC = max(nexC, i * 2 + 2); } else { tmp[rr][i * 2] = 0; tmp[rr][i * 2 + 1] = 0; } } for (int cc = 0; cc < nexC; cc++) { arr[rr][cc] = tmp[rr][cc]; } } } else { for (int cc = 0; cc < C; cc++) { int count[105] = { 0, }; for (int rr = 0; rr < R; rr++) { count[arr[rr][cc]]++; } for (int i = 1; i <= 100; i++) { if (count[i]) pq.push({ count[i], i }); } for (int i = 0; i < 100; i++) { if (!pq.empty()) { tmp[i * 2][cc] = pq.top().second; tmp[i * 2 + 1][cc] = pq.top().first; pq.pop(); nexR = max(nexR, i * 2 + 2); } else { tmp[i * 2][cc] = 0; tmp[i * 2 + 1][cc] = 0; } } for (int rr = 0; rr < nexR; rr++) { arr[rr][cc] = tmp[rr][cc]; } } } R = nexR; C = nexC; if (arr[r - 1][c - 1] == k) { flag = true; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> r >> c >> k; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { cin >> arr[i][j]; } } if (arr[r - 1][c - 1] == k) { cout << 0; return 0; } int count = 0; while (!flag && count++ <= 100) { solve(); } if (flag) { cout << count; } else { cout << -1; } return 0; }