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



문제에 제시된 대로 R연산 또는 C연산을 수행한 뒤에

정해진 위치에 k값이 있는지를 검사하면 된다.



행의 길이를 Y, 열의 길이를 X라고 했을 때

연산을 수행한 뒤에 나오는 값과 횟수를 sorting해주고 값을 수정한 뒤에

최종적으로 Y와 X의 길이를 업데이트 해주면된다.



횟수를 오름차순으로, 숫자를 오름차순으로 정렬해주기 위해

따로 구조체를 이용해서 정렬할 수 있도록 했다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100
 
int Y = 3;
int X = 3;
vector<vector<int>> map;
 
struct str {
    int value;
    int cnt;
    
    str(int value, int cnt) :value(value), cnt(cnt) {};
};
 
bool operator<(str s1, str s2) {
    if (s1.cnt != s2.cnt)
        return s1.cnt < s2.cnt;
    else
        return s1.value < s2.value;
    
}
int main() {
    
    int r, c, k;
    cin >> r >> c >> k;
    
    map = vector<vector<int>> (N, vector<int> (N, 0));
    
    for (int i = 0; i < Y; i++)
        for (int j = 0; j < X; j++)
            cin >> map[i][j];
    
    
    int ans = 0;
    while (true) {
        
        if (map[r - 1][c - 1] == k)
            break;
        
        if (ans > 100) {
            ans = -1;
            break;
        }
        
        int num[101] = { 0 };
        
        //R연산
        if (Y >= X) {
            for (int y = 0; y <= Y; y++) {
                
                memset(num, 0, sizeof(num));
                for (int x = 0; x <= X; x++) {
                    num[map[y][x]]++;
                    map[y][x] = 0;
                }
                
                vector<str> vec;
                for (int i = 1; i <= N; i++) {
                    if (num[i]) {
                        vec.push_back(str(i, num[i]));
                    }
                }
                
                sort(vec.begin(), vec.end());
                for (int i = 0,k=0; i < vec.size(); i++,k+=2) {
                    map[y][k] = vec[i].value;
                    map[y][k + 1] = vec[i].cnt;
                }
                
            }
        }
        else {    //C연산
            
            for (int x = 0; x <= X; x++) {
                
                memset(num, 0, sizeof(num));
                for (int y = 0; y <= Y; y++) {
                    num[map[y][x]]++;
                    map[y][x] = 0;
                }
                
                vector<str> vec;
                for (int i = 1; i <= N; i++) {
                    if (num[i]) {
                        vec.push_back(str(i, num[i]));
                    }
                }
                
                sort(vec.begin(), vec.end());
                for (int i = 0, k = 0; i < vec.size(); i++, k += 2) {
                    map[k][x] = vec[i].value;
                    map[k+1][x] = vec[i].cnt;
                }
                
            }
        }
        
        
        //y,x길이 새롭게
        int ny = 0;
        int nx = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j]) {
                    ny = max(ny, i);
                    nx = max(nx, j);
                }
            }
        }
        
        Y = ny;
        X = nx;
        ans++;
    }
    
    cout << ans << endl;
    
    return 0;
}
 
cs


저작자표시 변경금지

'알고리즘(BOJ) > 시뮬레이션' 카테고리의 다른 글

백준 14503번 - 로봇 청소기  (3) 2019.08.18
백준 3019번 - 테트리스  (1) 2019.07.21
백준 14890번 - 경사로  (0) 2019.07.03
백준 1764번 - 듣보잡  (0) 2019.05.14
백준 17144번 - 미세먼지 안녕!  (0) 2019.05.13

+ Recent posts

티스토리툴바