난이도 G4 / 체감 난이도 G4 / 소요시간 1H 30M
문제
크기가 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[1][1] A[1][2] → A[1][3] → A[1][4] → A[1][5] → A[1][6]
↑ ↓
A[2][1] A[2][2] A[2][3] → A[2][4] → A[2][5] A[2][6]
↑ ↑ ↓ ↓
A[3][1] A[3][2] A[3][3] A[3][4] A[3][5] A[3][6]
↑ ↑ ↓ ↓
A[4][1] A[4][2] A[4][3] ← A[4][4] ← A[4][5] A[4][6]
↑ ↓
A[5][1] A[5][2] ← A[5][3] ← A[5][4] ← A[5][5] ← A[5][6]
A[6][1] A[6][2] A[6][3] A[6][4] A[6][5] A[6][6]회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.
다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.
배열 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의 값의 최솟값을 출력한다.
제한
- 3 ≤ N, M ≤ 50
- 1 ≤ K ≤ 6
- 1 ≤ A[i][j] ≤ 100
- 1 ≤ s
- 1 ≤ r-s < r < r+s ≤ N
- 1 ≤ c-s < c < c+s ≤ M
풀이
- 회전 연산을 통해 값을 바꾸는 건 쉬웠으나, 안쪽으로 반복하여 계속 회전을 진행하다보니, 연산 값을 어떻게 설정해야할지 고민했었다.
- 회전 연산이 여러개일 경우, 각 연산을 실행하는 순서에 따라 결과값이 달라지므로, 이는 순열으로 처리를 하기로 하였다.
- 배열을 연산할 시에, 복사를 사용하지 않는다면 원 배열이 훼손이 되어 순열계산시에 배열이 망가지므로, 연산을 할 때 마다 복사한 배열을 생성해 이를 연산하고, 이 복사된 배열을 다시 원 배열로 옮기기로 하였다.
배열 복사하기
- 회전 연산을 하려면 먼저 배열을 복사할 필요가 있으므로 복사 메서드를 생성하였다.
public static int[][] copyMap() { int[][] tmp = new int[N][M]; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { tmp[i][j] = map[i][j]; // 원본이 삭제되면 안되므로. } } return tmp; } - 순열을 사용한다고 했으므로, 순열을 사용하되 count가 연산 수가 되면 사이클을 실행하도록 하였다.
public static void permu(int cnt, int[] arr, boolean check[]) { if (cnt == K) { doCycle(arr); return; } for (int i = 0; i < K; i++) { if (check[i]) { continue; } check[i] = true; arr[cnt] = i; permu(cnt + 1, arr, check); check[i] = false; // 끝나면 다시 f로 } } - count가 연산수에 도달하면 doCycle을 실행하는데, 이 때 한 연산을 돌면 다음엔 안쪽으로 회전을 돌아야한다
- 각 꼭짓점을 변수에 담아주고, 연산 수행 후, 다음 안쪽 연산을 위해 upTmp, rightTmp... 의 값을 바꾸어준다.
- downTmp의 경우 접근하지 않고 이미 값이 변해있을 것이므로 따로 선언하지 않는다.
public static void doCycle(int[] arr) { int[][] tmp = copyMap(); for (int k = 0; k < K; k++) { int r = cycle[arr[k]][0]; int c = cycle[arr[k]][1]; int S = cycle[arr[k]][2]; for (int s = 1; s <= S; s++) { // 위 int upTmp = tmp[r - s][c + s]; for (int y = c + s; y > c - s; y--) { tmp[r - s][y] = tmp[r - s][y - 1]; } // 오른쪽 int rightTmp = tmp[r + s][c + s]; for (int x = r + s; x > r - s; x--) { tmp[x][c + s] = tmp[x - 1][c + s]; } tmp[r - s + 1][c + s] = upTmp; // 아래 int leftTmp = tmp[r + s][c - s]; for (int y = c - s; y < c + s; y++) { tmp[r + s][y] = tmp[r + s][y + 1]; } tmp[r + s][c + s - 1] = rightTmp; // 왼쪽 for (int x = r - s; x < r + s; x++) { tmp[x][c - s] = tmp[x + 1][c - s]; } tmp[r + s - 1][c - s] = leftTmp; } } getAnswer(tmp); }
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M, K;
static int[][] cycle, map;
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
map = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
cycle = new int[K][3];
for (int k = 0; k < K; k++) {
st = new StringTokenizer(br.readLine());
cycle[k][0] = Integer.parseInt(st.nextToken()) - 1;
cycle[k][1] = Integer.parseInt(st.nextToken()) - 1;
cycle[k][2] = Integer.parseInt(st.nextToken());
}
int[] arr = new int[K];
boolean[] check = new boolean[K];
permu(0, arr, check);
System.out.printf("%d", min);
}
public static void permu(int cnt, int[] arr, boolean check[]) {
if (cnt == K) {
doCycle(arr);
return;
}
for (int i = 0; i < K; i++) {
if (check[i]) {
continue;
}
check[i] = true;
arr[cnt] = i;
permu(cnt + 1, arr, check);
check[i] = false; // 끝나면 다시 f로
}
}
public static int[][] copyMap() {
int[][] tmp = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
tmp[i][j] = map[i][j]; // 원본이 삭제되면 안되므로.
}
}
return tmp;
}
public static void doCycle(int[] arr) {
int[][] tmp = copyMap();
for (int k = 0; k < K; k++) {
int r = cycle[arr[k]][0];
int c = cycle[arr[k]][1];
int S = cycle[arr[k]][2];
for (int s = 1; s <= S; s++) {
// 위
int upTmp = tmp[r - s][c + s];
for (int y = c + s; y > c - s; y--) {
tmp[r - s][y] = tmp[r - s][y - 1];
}
// 오른쪽
int rightTmp = tmp[r + s][c + s];
for (int x = r + s; x > r - s; x--) {
tmp[x][c + s] = tmp[x - 1][c + s];
}
tmp[r - s + 1][c + s] = upTmp;
// 아래
int leftTmp = tmp[r + s][c - s];
for (int y = c - s; y < c + s; y++) {
tmp[r + s][y] = tmp[r + s][y + 1];
}
tmp[r + s][c + s - 1] = rightTmp;
// 왼쪽
for (int x = r - s; x < r + s; x++) {
tmp[x][c - s] = tmp[x + 1][c - s];
}
tmp[r + s - 1][c - s] = leftTmp;
}
}
getAnswer(tmp);
}
public static void getAnswer(int[][] tmp) { // 답 얻는 함수, 최소 합의 행..
for (int i = 0; i < N; i++) {
int sum = 0;
for (int j = 0; j < M; j++) {
sum += tmp[i][j];
}
if (min > sum) {
min = sum;
}
}
}
}결과
비고
- 문제 풀다가 회전 배열을 계산하는 법이 어려워서 블로그 글을 찾아 이해하였습니다.
- 출처 : https://koguri.tistory.com/97
'알고리즘' 카테고리의 다른 글
| [20125_쿠키의 신체 측정], Java (3) | 2025.01.03 |
|---|---|
| [프로그래머스] 붕대감기, JavaScript (0) | 2024.11.18 |
| 1520_내리막길 (Java) (0) | 2024.04.10 |
| 1405_미친로봇 (Java) (1) | 2024.04.01 |
| 1759_암호만들기 (Java) (0) | 2024.03.25 |