[BOJ] 17140 이차원 배열과 연산
Table Of Contents
1. 문제 요약
입력으로
r
c
k
{arr[r][c] = k}
{1 <= r, c, k <= 100}
초기 배열은 3x3이고, 1초마다 배열에 연산을 한 번씩 적용한다.
- 행의 개수 >= 열의 개수일 경우, 배열의 모든 행에 대해서 정렬을 수행한다.
- 행의 개수 < 열의 개수일 경우, 배열의 모든 열에 대해서 정렬을 수행한다.
여기에서 말하는 정렬 연산은 이렇게 정의된다.
- 각 행/열을 구성하는 수가 각각 몇 번 나왔는지 알아본다. (ex. 1이 1번, 2가 3번, 3이 1번, ...)
- 수의 등장 횟수를 오름차순으로, 등장 횟수가 같다면 수를 오름차순으로 정렬한다.
- 정렬된 결과를 배열 A에 다시 넣는다. 이 때, 각 행/열의 크기가 각각 다를 수 있다. 빈 칸에는 0을 넣는다. (0은 정렬할 때 무시된다.)
예를 들어서, 1, 1, 3
이라는 행이 있다면, 1이 2번, 3이 1번 나왔으므로 3, 1, 1, 2
처럼 정렬된다.
2. 풀이 정리
다음과 같은 점들을 보아 100초동안 모든 경우를 탐색하면 될 것 같았다.
- 100초를 넘어가면 더이상 연산을 수행하지 않는다
- r, c, k의 범위가 100 이하로 굉장히 작다
- 중간 연산의 결과로 만들어지는 배열도 200x200로 작은 편이다
- 배열에서 100을 넘어가는 숫자는 나오지 않을 것이다
R연산과 C연산을 언제 수행하는지가 명확하기 때문에,
{arr[r][c]}
k
나는 solve
함수에서 연산을 수행했다.
- 현재 행의 숫자()과 열의 숫자(
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; }