문제 탐색하기
입력 자료 정리
- n은 배열의 행열 크기를 의미한다
- 이후 들어오는 값들은 배열의 각 인덱스에 해당하는 원소이다
해결방법 추론
- n의 최대값이 20으로 작기 때문에, 팀을 뽑는 경우를 조합하거나
모든 경우에 대해 뽑는 부분집합 방식을 사용하면 문제를 해결할 수 있을 것이다 - 처음은 부분집합으로 풀었고, 학습을 목적으로 이후 살짝 변형하여 조합방식으로도 풀었다
부분집합
- 다시 문제로 돌아와서 base condition에 도달하면 정답을 찾기 위한 과정을 거쳐야한다
- 선택 여부는 방문 체크로 판단해서 각 팀의 인원 수를 세워준 뒤,
모두 1명 이상 선택 된 경우에 한해서 풀이를 이어나가면 될 것이다 - 이중포문을 돌면서 방문체크된 팀원끼리와 안된 팀원끼리에 대해 합산을 진행해주고,
그 차이를 구해준다 - 최소값을 찾기 위해 모든 경우에 대해 정답 변수와 비교해나간다면 정답을 구할 수 있을 것이다.
조합
- 부분집합 풀이 방식에서 살짝 변형해주면 된다.
- 1부터 n까지 뽑는 경우를 순회를 돌면서 모두 구해주면 된다.
- pick에 대한 파라미터를 통해 depth가 pick에 도달했을 때,
base condition 로직을 똑같이 진행해주면 된다.
시간복잡도 계산
- 시간복잡도는 부분집합의 경우 2^n의 연산이 발생할 것이고,
base condition에서 n^2의 연산이 발생한다 - 전체 시간복잡도는 O(2^n + n^2)이 될 것이고 시간제한안에 문제를 해결할 수 있다
코드 설계하기
입력값 상태 관리
- 크기를 나타내는 n은 변수로 관리하며, int형 2차원 배열에 각 인덱스 값들을 관리한다
구현 코드 설계
- 해결과정 추론에서 생각한 방식으로 코드를 구현하면된다.
- 조합과 부분집합의 방식의 차이만 고려하여 다르게 설계하면 된다
부분집합
- 부분집합은 뽑는 과정을 반복문 없이 재귀식을 두번 사용하여,
true일때와 false일때 재귀문을 실행하도록 한다.
각각, 현재 수를 어느 한 팀에 뽑는 경우와 안 뽑는 경우다. - depth가 n일때만을 base condition으로 한다.
조합
- 부분집합과 다르게 조합은 몇 명을 뽑을 지에 대해 1부터 n까지 순회를 돌면서 인수로 넘겨준다
- 조합은 n까지 순회하는 반복문을 순회한다.
단 중복을 제거하기 위해 반복문의 시작값을 이전 함수의 i+1값으로 초기화하도록 구현해주면 된다
출력값 설계
- 초기값이 Integer.MAX_VALUE로 되어있는 ans를
조합 혹은 부분집합의 결과에 따라 출력하면 정답이 된다.
정답코드
(부분 집합 풀이)
import java.io.*;
import java.util.*;
public class Main {
static int[][] arr;
static int ans = Integer.MAX_VALUE;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
arr = new int[n][n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
visited = new boolean[n];
backtracking(n, 0);
bw.write(ans+"");
br.close();
bw.close();
}
private static void backtracking(int n, int depth) {
if(depth == n){
int start = 0;
int link = 0;
for (int i = 0; i < n; i++) {
if(visited[i]){
start++;
}else{
link++;
}
}
if(start >= 1 && link >= 1){
int diff = solve(n);
ans = Math.min(ans, diff);
}
return;
}
visited[depth] = true;
backtracking(n, depth+1);
visited[depth] = false;
backtracking(n, depth+1);
}
private static int solve(int n) {
int start = 0;
int link = 0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if(visited[i] && visited[j]){
start += arr[i][j] + arr[j][i];
}
if(!visited[i] && !visited[j]){
link += arr[i][j] + arr[j][i];
}
}
}
return Math.abs(start - link);
}
}
(조합 풀이)
import java.io.*;
import java.util.*;
public class Main {
static int[][] arr;
static int ans = Integer.MAX_VALUE;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
arr = new int[n][n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
visited = new boolean[n];
for (int i = 1; i <= n; i++) {
backtracking(n, 0, 0, i);
}
bw.write(ans+"");
br.close();
bw.close();
}
private static void backtracking(int n, int depth, int now, int pick) {
if(depth == pick){
int start = 0;
int link = 0;
for (int i = 0; i < n; i++) {
if(visited[i]){
start++;
}else{
link++;
}
}
if(start >= 1 && link >= 1){
int diff = solve(n);
ans = Math.min(ans, diff);
}
return;
}
for (int i = now; i < n; i++) {
if(!visited[i]){
visited[i] = true;
backtracking(n, depth+1, i+1, pick);
visited[i] = false;
}
}
}
private static int solve(int n) {
int start = 0;
int link = 0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if(visited[i] && visited[j]){
start += arr[i][j] + arr[j][i];
}
if(!visited[i] && !visited[j]){
link += arr[i][j] + arr[j][i];
}
}
}
return Math.abs(start - link);
}
}
문제 링크
Software Developer