[C] 백준 17406번 : 배열 돌리기 4

문제

 

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

1 2 3 2 1 1 4 5 6

배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.

예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.

 

 

회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.

다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

 

배열 A	(3, 4, 2) 연산 수행 후	(4, 2, 1) 연산 수행 후
배열 A	(4, 2, 1) 연산 수행 후	(3, 4, 2) 연산 수행 후

 

배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.

배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

 

입력

 

첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.

둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.

 

출력

 

배열 A의 값의 최솟값을 출력한다.

 

풀이

 

#include <stdio.h>
#include <limits.h>
 
int arr[55][55];
int arr_copy[55][55];
int rotate[6][3]; // r,c,s
int order[6]={0,1,2,3,4,5};
int ans = INT_MAX;
int N,M,K;
 
void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
int array_val(){
    int min = INT_MAX;
 
    for(int i = 1 ; i <= N ; i++){
        int sum = 0;
        for(int j = 1 ; j <= M ; j++) sum += arr_copy[i][j];
        if(sum<min) min = sum;
    }
    return min;
}
 
void rorate_array(int r, int c, int s){
    // left top r-s,c-s
    // right bottom r+s,c+s 
    
    int tmp;
    for(int t = s ; t > 0 ; t--){
        tmp = arr_copy[r-t][c-t];
        int i = r-t;
        while(i<r+t){
            arr_copy[i][c-t] = arr_copy[i+1][c-t];
            i++;
        }
        i = c-t;
        while(i<c+t){
            arr_copy[r+t][i] = arr_copy[r+t][i+1];
            i++;
        }
        i = r+t;
        while(i>r-t){
            arr_copy[i][c+t] = arr_copy[i-1][c+t];
            i--;
        }
        i = c+t;
        while(i>c-t+1){
            arr_copy[r-t][i] = arr_copy[r-t][i-1];
            i--;
        }
        arr_copy[r-t][c-t+1] = tmp;
    }
}
 
void permutation(int n, int r){
    if(r==0){
        for(int i = 1 ; i <= N ; i++){
            for(int j = 1 ; j <= M ; j++) arr_copy[i][j]=arr[i][j];
        }
        for(int i = 0 ; i < K ; i++) 
            rorate_array(rotate[order[i]][0],rotate[order[i]][1],rotate[order[i]][2]);
        int val = array_val();
        if(val<ans) ans = val;
        return;
    }
    for(int i = n-1 ; i >= 0 ; i--){
        swap(&order[i],&order[n-1]);
        permutation(n-1,r-1);
        swap(&order[i],&order[n-1]);
    }
}
 
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++){
        scanf("%d %d %d",&rotate[i][0], &rotate[i][1], &rotate[i][2]);
    }
    permutation(K,K);
    printf("%d\n",ans);
}

 

삼성 SW 역량 테스트 기출 문제!

디버깅 열심히 했다...

배열의 최소 값을 구해야 하므로 먼저 배열의 값을 구하는 함수를 만들어보았다

array_val이라는 함수로 각 행에 있는 모든 수의 합을 비교해서 가장 작은 값을 return 해주었다

 

회전함수는 swap 함수 처럼 한칸에 미리 저장해놓고 그 칸부터 땡겨주었다

index 실수만 하지 않는다면 금방 구현 가능하다

 

실제 회전 후 배열의 값을 구하는건 순열 함수를 이용하였다

순열 함수로 회전의 가능한 순서 조합을 전부 찾아 실제로 회전을 시킨 후 배열의 값을 구해보았다

구한 배열의 값이 작다면 ans를 갱신해주었다

입력 받은 array를 permutation에서 돌렸다가 원상복귀 시키는 것보다 새로 복사해서 쓰고 버리는게 빠를 것 같아 arr_copy 배열로 회전 시켜주었다