반응형

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

 

17406번: 배열 돌리기 4

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

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 연산의 개수를 저장할 구조체를 만들고 배열에 연산을 저장합니다.

 

2. 순열을 뽑아서 연산을 진행하면서 최솟값을 ans에 저장합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
struct pos {
    int r;
    int c;
    int s;
};
 
int N, M, K;
int arr[51][51];
pos cal[6];
int visited[6];
int ans = 987654321;
 
void lotate(pos cur)    //배열 돌리가
{
    int r, c, s;
    r = cur.r;
    c = cur.c;
    s = cur.s;
 
    
    for (int i = s; i > 0; i--) {
        int temp = arr[r - i][c - i];
        for (int j = r - i; j < r + i; j++) {
            arr[j][c - i] = arr[j + 1][c - i];
        }
        for (int j = c - i; j < c + i; j++) {
            arr[r + i][j] = arr[r + i][j + 1];
        }
        for (int j = r + i; j > r - i; j--) {
            arr[j][c + i] = arr[j - 1][c + i];
        }
        for (int j = c + i; j > c - i; j--) {
            arr[r - i][j] = arr[r - i][j - 1];
        }
        arr[r - i][c - i + 1] = temp;
    }
 
    int de = -1;
}
 
void dfs(int level)    //순열 뽑기
{
    if (level == K) {
        for (int i = 1; i <= N; i++) {
            int sum = 0;
            for (int j = 1; j <= M; j++) {
                sum += arr[i][j];
            }
            ans = min(ans, sum);
        }
        return;
    }
 
    int temp[51][51] = { 0 };
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    for (int i = 0; i < K; i++) {
        if (visited[i] == 0) {
            visited[i] = 1;
            lotate(cal[i]);
            dfs(level + 1);
            visited[i] = 0;
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    arr[i][j] = temp[i][j];
                }
            }
        }
    }
}
 
int main()
{
    scanf("%d %d %d", &N, &M, &K);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 0; i < K; i++) {
        int r, c, s;
        scanf("%d %d %d", &r, &c, &s);
        cal[i] = { r,c,s };
    }
 
    dfs(0);
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 23291번 - 어항 정리 (C++)  (0) 2022.10.10
[ 백준 ] 5014번 - 스타트링크 (C++)  (0) 2022.10.09
[ 백준 ] 17281번 - ⚾ (C++)  (0) 2022.10.07
[ 백준 ] 17136번 - 색종이 붙이기 (C++)  (0) 2022.10.06
[ 백준 ] 23290번 - 마법사 상어와 복제 (C++)  (0) 2022.10.05

+ Recent posts

티스토리툴바