문제 - https://www.acmicpc.net/problem/17406
17406번: 배열 돌리기 4
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의
www.acmicpc.net
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
static int N, M, K, min = Integer.MAX_VALUE;
static int[][] arr, info, copy, tmp;
static boolean[] picked;
static Stack<Integer> jobq = new Stack<>();
public static void main(String[] args) throws IOException{
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
arr = new int[N][M];
copy = new int[N][M];
tmp = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
info = new int[K][3];
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
info[i][0] = Integer.parseInt(st.nextToken())-1;
info[i][1] = Integer.parseInt(st.nextToken())-1;
info[i][2] = Integer.parseInt(st.nextToken());
}
picked = new boolean[K];
pick(K);
bw.write(min+"\n");
bw.flush();
bw.close();
br.close();
}
static void pick(int remain){
if(remain==0){
calc();
return;
}
for (int i = 0; i < K; i++) {
if(!picked[i]){
picked[i] = true;
jobq.add(i);
pick(remain-1);
jobq.pop();
picked[i] = false;
}
}
}
static void calc() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
copy[i][j] = arr[i][j];
}
}
for(Integer i : jobq){
rotate(info[i][0], info[i][1], info[i][2]);
}
for (int i = 0; i < N; i++) {
int sum = 0;
for (int j = 0; j < M; j++) {
sum += copy[i][j];
}
min = Math.min(min, sum);
}
}
static void rotate(int r, int c, int s){
if(s==0) return;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
tmp[i][j] = copy[i][j];
}
}
for (int i = 0; i < 2*s; i++) {
copy[r-s][c-s+i+1] = tmp[r-s][c-s+i];
}
for (int i = 0; i < 2*s; i++) {
copy[r-s+i+1][c+s] = tmp[r-s+i][c+s];
}
for (int i = 0; i < 2*s; i++) {
copy[r+s][c+s-i-1] = tmp[r+s][c+s-i];
}
for (int i = 0; i < 2*s; i++) {
copy[r+s-i-1][c-s] = tmp[r+s-i][c-s];
}
rotate(r, c, s-1);
}
}
단순 구현문제 같으면서도 생각보다 퍼포먼스가 나오지않는걸 보니 뭔가 알고리즘 최적화가 필요한 것 같다...ㅠㅠ
'공부 > algorithm' 카테고리의 다른 글
| BOJ N번째 큰 수(2075) - Java (0) | 2021.12.23 |
|---|---|
| BOJ 토마토(7576) - Java (0) | 2021.12.20 |
| BOJ 연구소 3(17142) - Java (0) | 2021.11.18 |
| BOJ 빙산(2573) - Java (0) | 2021.11.18 |
| BOJ 나무 재테크(16235) - Java (0) | 2021.11.17 |