[17406번] 배열 돌리기4

17406번: 배열 돌리기 4

 

www.acmicpc.net

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다.

회전연산 이란, 아래 그림 처럼 배열을 회전시키는 연산이다.

주어진 회전 연산의 정보에 따라 회전한 배열 A의 값중 최소값을 출력하는 문제다.

구현력을 보는 문제인듯 하다.

1. 회전 연산의 순서를 정하고 (순열)

2. 정해진 순서에 맞춰 회전 연산을 수행 (회전)

3. 연산이 끝난 배열의 값을 구해서 최소값을 구한다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>
#include <string.h>
using namespace std;
struct info { int r, c, s; };
int map[51][51];
info cmd[6];
int N, M, K, ans = INT_MAX;
 
 
void rotate(int rr, int cc, int len) {
    int r = rr;
    int c = cc;
    int prev = map[r][c];
    int tmp;
 
    c++;
    while (c < cc + len) {
        tmp = map[r][c];
        map[r][c] = prev;
        prev = tmp;
        c++;
    }
    c--;
 
    r++;
    while (r < rr + len) {
        tmp = map[r][c];
        map[r][c] = prev;
        prev = tmp;
        r++;
    }
    r--;
 
    c--;
    while (cc <= c) {
        tmp = map[r][c];
        map[r][c] = prev;
        prev = tmp;
        c--;
    }
    c++;
 
    r--;
    while (rr <= r) {
        tmp = map[r][c];
        map[r][c] = prev;
        prev = tmp;
        r--;
    }
    r++;
}
 
void perm(int idx) {
    if (idx == K) {
        int tmp[51][51];
        memcpy(tmp, map, sizeof(tmp));
        for (int i = 0; i < K; i++)
            for (int j = 1; j <= cmd[i].s; j++)
                rotate(cmd[i].r - j, cmd[i].c - j, j*2+1);
 
        for (int r = 1; r <= N; r++) {
            int sum = 0;
            for (int c = 1; c <= M; c++) 
                sum += map[r][c];
            ans = sum < ans ? sum : ans;
        }
        memcpy(map, tmp, sizeof(tmp));
        return;
    }
    for (int i = 0; i < K; i++) {
        swap(cmd[i], cmd[idx]);
        perm(idx + 1);
        swap(cmd[i], cmd[idx]);
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> M >> K;
    for (int r = 1; r <= N; r++) 
        for (int c = 1; c <= M; c++) 
            cin >> map[r][c];
    for (int i = 0; i < K; i++) {
        int r, c, s;
        cin >> r >> c >> s;
        cmd[i] = { r,c,s };
    }
    perm(0);
 
    cout << ans;
    return 0;
}