시뮬레이션과 구현

배열 돌리기 4

4gats 2023. 9. 18. 15:36

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

 

17406번: 배열 돌리기 4

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의

www.acmicpc.net

 

https://larc-en-ciel.tistory.com/162

 

배열 돌리기 1

https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ←

larc-en-ciel.tistory.com

여기에다가 next_permutation만 추가하면 끝!

의문사를 당했다

3 ≤ N, M ≤ 50

이어서 48개네? 해서 

배열크기를 50으로 잡았다...

 

의문사를 당할 땐

배열 크기도 확인해보자.

아니 그전에 배열을 걍 넉넉하게 잡자

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
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
int ans = 100 * 50;
int n, m, k;
bool chk[55][55];
int ori_arr[55][55];
int change_arr[55][55];
int tmp[55][55];
 
struct info {
    int row;
    int column;
    int si;
};
 
int calculate()
{
    vector<int> possible_min;
    int jujang;
    for (int i = 1; i <= n; i++)
    {
        jujang = 0;
        for (int j = 1; j <= m; j++)
        {
            jujang += change_arr[i][j];
        }
        possible_min.push_back(jujang);
    }
    return *min_element(possible_min.begin(), possible_min.end());
}
 
void rotate(int r, int c, int s)
{
    memcpy(&tmp, &change_arr, sizeof(change_arr));
 
    for (int minus = 1; minus <= s; minus++)
    {
        int start_row = r - minus;
        int start_col = c - minus;
        
        int x = start_row;
        int y = start_col;
 
        while (!chk[x][y])
        {
            chk[x][y] = true;
 
            // 오른쪽
            if (x == start_row && y != c + minus)
            {
                change_arr[x][y + 1] = tmp[x][y];
                y++;
            }
            // 아래
            else if (y == c + minus && x != r + minus)
            {
                change_arr[x + 1][y] = tmp[x][y];
                x++;
            }
            // 왼쪽
            else if (x == r + minus && y != c - minus)
            {
                change_arr[x][y - 1] = tmp[x][y];
                y--;
            }
            // 위
            else if (x != r - minus && y == c - minus)
            {
                change_arr[x - 1][y] = tmp[x][y];
                x--;
            }
        }
 
    }
 
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> ori_arr[i][j];
        }
    }
 
    vector<info> sunseo;
    vector<int> dolrigi;
    for (int i = 0; i < k; i++)
    {
        dolrigi.push_back(i);
        int r, c, s;
        cin >> r >> c >> s;
        sunseo.push_back({ r, c, s });
    }
    
    do {
        memcpy(&change_arr, &ori_arr, sizeof(ori_arr));
        for (int i = 0; i < dolrigi.size(); i++)
        {
            info ahn;
            ahn = sunseo[dolrigi[i]];
            rotate(ahn.row, ahn.column, ahn.si);
            
            memset(chk, false, sizeof(chk));
        }
 
        if (ans > calculate())
            ans = calculate();
 
    } while (next_permutation(dolrigi.begin(), dolrigi.end()));
 
    cout << ans << '\n';
    
    
 
 
    return 0;
}
 cs