OJ
[SWEA] 4012 요리사 (JAVA)
P3PP4
2022. 8. 13. 22:04
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
핵심은 (N이 4보다 높을 때) 고른 식재료에 대한 서로의 시너지 전체를 구해야 한다는 것이라고 생각합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static int T, N, half, result;
static int[] numbers1, numbers2;
static int[][] arr;
static boolean[] isUsed;
public static void main(String[] args) throws IOException {
T = Integer.parseInt(br.readLine());
for (int testCase = 1; testCase <= T; testCase++) {
N = Integer.parseInt(br.readLine());
half = N / 2;
numbers1 = new int[half];
numbers2 = new int[half];
isUsed = new boolean[N];
arr = new int[N][N];
result = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
} /* 입력 끝 */
pick(0, 0);
sb.append("#").append(testCase).append(" ").append(result).append("\n");
}
System.out.print(sb);
}
static void pick(int cnt, int start) {
if(cnt == half) {
// half개 뽑았을 때 로직
for (int i = 0; i < half; i++) {
for (int j = 0; j < N; j++) {
if(isUsed[j] == true) continue;
isUsed[j] = true;
numbers2[i] = j;
break;
}
}
int s1 = 0;
int s2 = 0;
for (int i = 0; i < half; i++) {
for (int j = i + 1; j < half; j++) {
s1 += arr[numbers1[i]][numbers1[j]];
s1 += arr[numbers1[j]][numbers1[i]];
s2 += arr[numbers2[i]][numbers2[j]];
s2 += arr[numbers2[j]][numbers2[i]];
}
}
int temp = Math.abs(s1 - s2);
if(temp < result) result = temp;
// 되돌려놓기
for (int i = 0; i < half; i++) {
isUsed[numbers2[i]] = false;
}
return;
}
for (int i = start; i < N; i++) {
numbers1[cnt] = i;
isUsed[i] = true;
pick(cnt + 1, i + 1);
isUsed[i] = false;
}
}
}