백준 17140: 이차원 배열과 연산

이차원 배열과 연산

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

512 MB

13851

6395

4124

43.147%

문제

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

입력

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

예제 입력 1 복사

1 2 2
1 2 1
2 1 3
3 3 3

예제 출력 1 복사

0

예제 입력 2 복사

1 2 1
1 2 1
2 1 3
3 3 3

예제 출력 2 복사

1

예제 입력 3 복사

1 2 3
1 2 1
2 1 3
3 3 3

예제 출력 3 복사

2

예제 입력 4 복사

1 2 4
1 2 1
2 1 3
3 3 3

예제 출력 4 복사

52

예제 입력 5 복사

1 2 5
1 2 1
2 1 3
3 3 3

예제 출력 5 복사

-1

예제 입력 6 복사

3 3 3
1 1 1
1 1 1
1 1 1

예제 출력 6 복사

2

힌트

배열 A의 초기값이 아래와 같은 경우를 생각해보자.

1 2 1
2 1 3
3 3 3

가장 처음에는 행의 개수 ≥ 열의 개수 이기 때문에, R 연산이 적용된다. 편의상 정렬 중간 단계는 (수, 수의 등장 횟수)로 표현한다.

1 2 1 → (2, 1), (1, 2)         → 2 1 1 2
2 1 3 → (1, 1), (2, 1), (3, 1) → 1 1 2 1 3 1
3 3 3 → (3, 3)                 → 3 3

크기가 가장 큰 행은 2번 행이고, 나머지 행의 뒤에 0을 붙여야 한다.

2 1 1 2 0 0
1 1 2 1 3 1
3 3 0 0 0 0

다음에 적용되는 연산은 행의 개수 < 열의 개수이기 때문에 C 연산이다. 

1 3 1 1 3 1
1 1 1 1 1 1
2 1 2 2 0 0
1 2 1 1 0 0
3 0 0 0 0 0
1 0 0 0 0 0

연산이 적용된 결과는 위와 같다.

출처

• 문제를 만든 사람: baekjoon
• 어색한 표현을 찾은 사람: djm03178, jh05013

테케부터 걸려서 포기한 문제이니 밑에 나오는 코드는 무용지물입니다!

사고 과정

3 1 1
3 1 1 2
3 한번 1 
2 한번 1
1 두번 2
2 1 3 1 1 2
R 연산 모든 행에 대한 정렬 수행
C 연산 모든 열에 대한 정렬 수행

정렬방법 각 수가 몇번 나왔는지 알아야한다
그 다음
수의 등장 횟수가 커지는 순으로 이런게 여러가지면 커지는 순으로 정렬한다
그 다음 정렬된 결과를 다시 넣는다.
정렬된 결과를 배열에 넣을 때는 수와 등장 횟수를 모두 넣으며 순서는 수가 먼저이다.

움 문제이해했다.
1 1 2 1 3 1 이 있으면 1 4 2 1 3 1 요렇게 정렬하란 말이다.
코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int r, c, k;
int arr[101][101];

bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.second != b.second)
return a.second < b.second;
else if (a.second == b.second)
return a.first < b.first;
}

void R(int y) {//행에 대해서 정렬을 수행한다.
vector<int>v;
vector<pair<int, int>> p_v;
for (int i = 1; arr[y][i] != 0; i++) {
v.push_back(arr[y][i]);
arr[y][i] = 0;
}
sort(v.begin(), v.end());
for (int i = 0; i < v.size();) {
int cr = v[i];
int idx = 1;//더해줄 인덱스
int jump = i + 1;//다음인덱스랑 비교할 것들
while (1) {
if (jump == v.size())break;
if (cr != v[jump])break;
jump++;
idx++;
}
p_v.push_back({ v[i],idx });
i += idx;
}
sort(p_v.begin(), p_v.end(), cmp);
int k = 1;
for (int i = 0; i < p_v.size(); i++) {
if (k > 100)break;
arr[y][k++] = p_v[i].first;
if (k > 100)break;
arr[y][k++] = p_v[i].second;
}
}
void C(int x) {//열에 대해서 정렬을 수행한다.
vector<int>v;
vector<pair<int, int>> p_v;
for (int i = 1; arr[i][x] != 0; i++) {
v.push_back(arr[i][x]);
arr[i][x] = 0;
}

sort(v.begin(), v.end());

for (int i = 0; i < v.size();) {
int cr = v[i];
int idx = 1;//더해줄 인덱스
int jump = i + 1;//다음인덱스랑 비교할 것들
while (1) {
if (jump == v.size())break;
if (cr != v[jump])break;
jump++;
idx++;
}
p_v.push_back({ v[i],idx });
i += idx;
}
sort(p_v.begin(), p_v.end(), cmp);
int k = 1;
for (int i = 0; i < p_v.size(); i++) {
if (k > 100)break;
arr[k++][x] = p_v[i].first;
if (k > 100)break;
arr[k++][x] = p_v[i].second;
}
}
int solve() {
int ret = 0;
while (1) {
if (arr[r][c] == k)break;
int a, b;//열 행
for (int i = 1; i <= 100; i++) {
if (arr[1][i] == 0) {
a = i;
break;
}
}
for (int i = 1; i <= 100; i++) {
if (arr[i][1] == 0) {
b = i;
break;
}
}
if (a <= b) {
for (int i = 1; arr[i][1] != 0; i++) {
R(i);
}
}
else {
for (int i = 1; arr[1][i] != 0; i++) {
C(i);
}
}
ret++;
if (ret == 100)
{
ret = -1;
break;
}
}
return ret;
}
int main() {
cin >> r >> c >> k;
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
cin >> arr[i][j];

cout << solve();
return 0;
}

이렇게짰는데 실패...ㅎㅎ 다음에 다시 풀어서 제대로 된 코드로 오겠당. 그 전에는 풀기가 넘모 싫다 이문제... 

제대로된 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int arr[100][100];
int r, c, k;

int solve() {

    int rsize = 3, csize = 3;

    for (int t = 0; t <= 100; t++) {
        if (arr[r][c] == k) {
            return t;
        }

        if (rsize >= csize) {
            for (int i = 0; i < rsize; i++) {
                vector <pair<int, int>> nums;
                nums.clear();
                int cnt[101] = { 0, };
                for (int j = 0; j < csize; j++) {
                    cnt[arr[i][j]]++;
                }
                for (int c = 1; c <= 100; c++) {
                    if (cnt[c] > 0) {
                        nums.push_back({ cnt[c],c });
                    }
                }
                sort(nums.begin(), nums.end());
                int idx = 0;
                for (auto pair : nums) {
                    if (idx >= 99) break;
                    arr[i][idx++] = pair.second;
                    arr[i][idx++] = pair.first;
                }
                csize = max(csize, idx);
                for (; idx < 100; idx++) {
                    arr[i][idx] = 0;
                }
            }
        }
        else {
            for (int j = 0; j < csize; j++) {
                vector <pair<int, int>> nums;
                nums.clear();
                int cnt[101] = { 0, };
                for (int i = 0; i < rsize; i++) {
                    cnt[arr[i][j]]++;
                }
                for (int c = 1; c <= 100; c++) {
                    if (cnt[c] > 0) {
                        nums.push_back({ cnt[c],c });
                    }
                }
                sort(nums.begin(), nums.end());
                int idx = 0;
                for (auto pair : nums) {
                    if (idx >= 99) break;
                    arr[idx++][j] = pair.second;
                    arr[idx++][j] = pair.first;
                }
                rsize = max(rsize, idx);
                for (; idx < 100; idx++) {
                    arr[idx][j] = 0;
                }
            }
        }
    }
    return -1;

}

int main() {
    cin >> r >> c >> k;
    r--;
    c--;

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> arr[i][j];
        }
    }

    cout << solve();

    return 0;
}