728x90
https://www.acmicpc.net/problem/17406
17406번: 배열 돌리기 4
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의
www.acmicpc.net
삼성A형 구현 정말 길구나..
푼 방법은 일단 완전탐색 기본에
1. 입력 정보를 저장함
2. 각 회전 방법들을 순열을 써서 서로 다른 경우로 쪼개줌
3. 각 경우별로 회전을 시행하고
4. 최소값을 계산해줌
알고리즘은 쉬운데 구현이어려워
|
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
|
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m, k;
//0 = r , 1 = c , 2 = s
int roll[7][3];
int arr[51][51];
//복사용 배열 brr과 crr
int brr[51][51];
int crr[51][51];
int selec[7];
//조합 수 저장 배열
int permu[7];
int answer = 987654321;
void calculate() {
for (int i = 1; i <= n; i++) {
int sum = 0;
for (int j = 1; j <= m; j++) {
sum += brr[i][j];
}
answer = min(sum, answer);
}
}
//회전시키는 함수
void gogo() {
//가상의 배열을 복사해서 박음
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
brr[i][j] = arr[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
crr[i][j] = arr[i][j];
//순열 첫 자리부터 k번자리까지 접근
for (int i = 1; i <= k; i++) {
// j는 멀어진 거리
for (int j = roll[permu[i]][2]; j >= 1; j--) {
//센터행
int ch = roll[permu[i]][0];
//센터열
int cy = roll[permu[i]][1];
//맨 윗줄 돌리기
for (int k = cy - j; k < cy + j; k++)
brr[ch - j][k + 1] = crr[ch - j][k];
//오른쪽 돌리기
for (int k = ch - j; k < ch + j; k++)
brr[k + 1][cy + j] = crr[k][cy + j];
//아래 돌리기
for (int k = cy + j; k > cy - j; k--)
brr[ch + j][k - 1] = crr[ch + j][k];
//왼쪽 돌리기
for (int k = ch + j; k > ch - j; k--)
brr[k - 1][cy - j] = crr[k][cy - j];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
crr[i][j] = brr[i][j];
}
calculate();
}
//순열 구하는 함수
void dfs(int cnt) {
if (cnt == k + 1) {
gogo();
return;
}
for (int i = 1; i <= k; i++) {
if (selec[i] == true) continue;
selec[i] = true;
//cnt번째 숫자가 i임
permu[cnt] = i;
dfs(cnt + 1);
selec[i] = false;
}
}
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> arr[i][j];
for (int i = 1; i <= k; i++)
for (int j = 0; j < 3; j++)
cin >> roll[i][j];
dfs(1);
cout << answer;
return 0;
}
|
cs |
728x90
'PS > 백준' 카테고리의 다른 글
| [백준 11053번] 가장 긴 증가하는 부분 수열 파이썬/python (0) | 2021.06.10 |
|---|---|
| [백준 17135번] 캐슬 디펜스 c++ (0) | 2021.05.18 |
| [백준 17471번] 게리맨더링 C++ (0) | 2021.05.16 |
| [백준 17281번] ⚾(야구) C++ (1) | 2021.05.16 |
| [백준 17070번] 파이프 옮기기 1 C++ (0) | 2021.05.14 |
