Gi-Log

백준(BOJ) 17140 이차원 배열과 연산 C++ 풀이 본문

알고리즘 BOJ

백준(BOJ) 17140 이차원 배열과 연산 C++ 풀이

돌잔 2021. 8. 21. 22:44

문제 링크: https://www.acmicpc.net/problem/17140

 

17140번: 이차원 배열과 연산

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

www.acmicpc.net

풀이에 이용된 알고리즘: 구현, 시뮬레이션

 

문제에 주어진 대로 구현하면 쉽게 풀리는 문제였던 것으로 기억한다.

 

처음 입력 시 arr[r][c] == k 라면 추가적인 탐색없이 0을 출력할 수 있도록 하는 로직을 넣어주지 않아서 시간을 낭비했었다.

 

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
125
126
127
128
129
130
131
132
133
134
135
136
137
/* BOJ 17140 이차원 배열과 연산 */
 
#include <iostream>
#include <functional>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <string.h>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
int r, c, k, r_cnt = 3, c_cnt = 3;
int arr[101][101], check[101];
 
bool cmp(pair<intint> p1, pair<intint> p2)
{
    if (p1.second != p2.second)
        return p1.second < p2.second;
    else
        return p1.first < p2.first;
}
 
void R_calc()
{
    for (int i = 1; i <= r_cnt; i++// 행 by 행으로 적용
    {
        memset(check, 0x00sizeof(check)); // 등장횟수 체크용 배열 초기화
 
        for (int j = 1; j <= c_cnt; j++)
            if (arr[i][j] != 0)
                check[arr[i][j]]++// 등장 회수 하나 증가
 
        vector<pair<intint>> tmp;
        for (int j = 1; j < 101; j++)
        {
            if (!check[j])
                continue;
 
            tmp.push_back({j, check[j]});
        }
 
        sort(tmp.begin(), tmp.end(), cmp);
 
        c_cnt = max(c_cnt, int(tmp.size()) * 2);
 
        memset(arr[i], 0x00sizeof(arr[i]));
        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_calc()
{
    for (int j = 1; j <= c_cnt; j++// 행 by 행으로 적용
    {
        memset(check, 0x00sizeof(check)); // 등장횟수 체크용 배열 초기화
 
        for (int i = 1; i <= r_cnt; i++)
            if (arr[i][j] != 0)     // 0이 등장하면 break
                check[arr[i][j]]++// 등장 회수 하나 증가
 
        vector<pair<intint>> tmp;
        for (int i = 1; i < 101; i++)
        {
            if (!check[i])
                continue;
 
            tmp.push_back({i, check[i]});
        }
 
        sort(tmp.begin(), tmp.end(), cmp);
 
        r_cnt = max(r_cnt, int(tmp.size()) * 2);
 
        for (int i = 1; i < 101; i++)
            arr[i][j] = 0;
 
        for (int i = 0; i < tmp.size(); i++)
        {
            arr[i * 2 + 1][j] = tmp[i].first;
            arr[(i + 1* 2][j] = tmp[i].second;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    freopen("input.txt""r", stdin);
 
    cin >> r >> c >> k;
 
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            cin >> arr[i][j];
 
    int sec = 0;
    if (arr[r][c] == k)
    {
        cout << 0 << endl;
        return 0;
    }
 
    while (true)
    {
        sec += 1// 1초 지날 때 마다 r 또는 c 연산
 
        if (r_cnt >= c_cnt) // R 연산
            R_calc();
        else
            C_calc();
 
        if (arr[r][c] == k) // 탈출 조건
            break;
 
        if (sec == 100// 100초째에 R, C 연산을 하고도 위 탈출조건을 만족하지못한 경우
        {
            cout << -1 << endl;
            return 0;
        }
    }
 
    cout << sec << '\n';
 
    return 0;
}
cs

 

Comments