728x90
문제
https://www.acmicpc.net/problem/15661
어떻게 풀 것인가?
처음에는 부분집합을 통한 방법을 생각했다.
부분집합을 이용해서 팀을 나누는 방식을 생각했다. 이는 부분집합이 선택되고, 선택되지 않고 하는 방식이기 때문이었다. 하지만 코드에 대한 아이디어가 잘 떠오르지 않아서, 백트레킹 방법으로 다가갔다.
아래는 풀이에 대한 아이디어 접근이다.
- 모든 조합을 만들어보고 능력치 계산해서 최솟값을 갱신하는 백트래킹 or 브루트포스 방식 사용.
- visited[] 배열을 활용해 팀을 나눈다.
- 한 팀이 정해지면 나머지는 자동으로 다른 팀이 된다.
- 조합(Combination)으로 팀을 나누고, 능력치를 계산해서 차이를 구한다.
- 최솟값으로 계속 갱신한다.
- N/2까지만 조합을 구하면 중복을 막을 수 있다.
풀면서 놓쳤던점
백트레킹은 항상 어려운 것 같다..
이 문제를 통해 얻어갈 것
백트레킹을 통한 브루트 포스 접근법
내 코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int[][] S;
static boolean[] visited;
static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
S = new int[N][N];
visited = new boolean[N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
S[i][j] = Integer.parseInt(st.nextToken());
}
}
// 팀 인원 수는 1명 이상 N/2명 이하
for (int i = 1; i <= N / 2; i++) {
combination(0, 0, i);
}
System.out.println(answer);
}
// 팀 조합을 만드는 메소드 (백트래킹)
static void combination(int depth, int start, int r) {
if (depth == r) {
List<Integer> startTeam = new ArrayList<>();
List<Integer> linkTeam = new ArrayList<>();
for (int i = 0; i < N; i++) {
if (visited[i]) startTeam.add(i);
else linkTeam.add(i);
}
int startSum = 0, linkSum = 0;
for (int i = 0; i < r; i++) {
for (int j = i + 1; j < r; j++) {
int a = startTeam.get(i);
int b = startTeam.get(j);
startSum += S[a][b] + S[b][a];
}
}
for (int i = 0; i < N - r; i++) {
for (int j = i + 1; j < N - r; j++) {
int a = linkTeam.get(i);
int b = linkTeam.get(j);
linkSum += S[a][b] + S[b][a];
}
}
answer = Math.min(answer, Math.abs(startSum - linkSum));
return;
}
for (int i = start; i < N; i++) {
visited[i] = true;
combination(depth + 1, i + 1, r);
visited[i] = false;
}
}
}
참고
X
728x90
'BaekJoon' 카테고리의 다른 글
| [BaekJoon] 17471번 게리맨더링 (Java) 문제 풀이 [Gold 3] (0) | 2025.05.19 |
|---|---|
| [BaekJoon] 4485번 녹색 옷 입은 애가 젤다지? (Java) 문제 풀이 [Gold 4] (0) | 2025.05.19 |
| [BaekJoon] 8111번 0과 1 (Java) 문제 풀이 [Platinum 5] (0) | 2025.02.28 |
| [BaekJoon] 15683번 감시 (Java) 문제 풀이 [Gold 3] (0) | 2025.02.27 |
| [BaekJoon] 1655번 가운데를 말해요. (Java) 문제 풀이 [Gold 2] (0) | 2025.02.20 |