오늘은 백트래킹 문제를 풀어보았다.
https://www.acmicpc.net/problem/14889
해당 문제는 어떻게 푸는게 좋을지 생각을 해보자
1. A팀의 인원을 선별하게 되면 나머지는 자동적으로 B팀이라고 가정하면 된다.
2. A팀을 예시로 1 2 5로 뽑나, 5 2 1 로 뽑나 같은 경우의 수로 해당 중복 케이스는 진행하지 않는 방향으로 구성하면 된다.
하여 뽑힌 A팀의 인원의 능력치와 B팀의 능력치를 구하여 비교한 최소값을 해로 구하면 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int answer = Integer.MAX_VALUE;
static int N;
static int[][] map;
public static void main(String[] args) throws IOException {
solution();
}
public static void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
map = new int[N][N];
boolean[] team = new boolean[N];
for (int i=0 ; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j=0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
backtracking(-1, team, N/2);
System.out.println(answer);
}
public static void backtracking(int prev, boolean[] team, int count) {
if (count == 0) {
int scoreA = 0;
int scoreB = 0;
for (int i=0; i < N; i++) {
if (team[i]) {
scoreA += add(team, team[i], i);
} else {
scoreB += add(team, team[i], i);
}
}
answer = Math.min(answer, Math.abs(scoreA - scoreB));
return;
}
for (int i=prev+1; i < N; i++) {
team[i] = true;
backtracking(i, team, count - 1);
team[i] = false;
}
}
public static int add(boolean[] team, boolean type, int num) {
int score = 0;
for (int i=0; i < N; i++) {
if (team[i] == type) {
score += map[num][i];
}
}
return score;
}
}
결과
'Coding Test' 카테고리의 다른 글
백준 휴먼 파이프라인(22981) (0) | 2024.03.25 |
---|---|
백준 체스(9204) (0) | 2024.03.24 |
백준 나이트의 이동(7562) (1) | 2024.03.20 |
백준 점프왕 쩰리 (Large)(16174) (0) | 2024.03.18 |
백준 보드점프(3372) (2) | 2024.03.17 |