[백준] 15661번 링크와 스타트 JAVA (자바) 풀이

문제 15661  (비트마스킹)

 

 :  축구는 평일 오후에 하고 의무 참석도 아니다.

 

 :  축구를 하기 위해 모인 사람은 총 N명, 이제 스타트 팀과 링크 팀으로 사람들을 나눈다. (한 명 이상)

 

 :  번호를 1부터 N까지로 배정했고 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다.

    팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. 

 

 

  (예시) N=4이고, S가 아래와 같은 경우를 살펴보자.

 

 

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

 

 

 

 [코드]

import java.io.*;
import java.util.*;

public class Main {
    static int N, result;		
    static int[][] player;		
    static boolean[] visit;		
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        player = new int[N][N];

        for(int i = 0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j<N; j++){
                player[i][j] = Integer.parseInt(st.nextToken());
            }
        }
		
        result = Integer.MAX_VALUE;
        visit = new boolean[N];
        solve(0);
        System.out.println(result);
    }
	
    static void solve(int cnt){
        if(cnt == N){
            int start = 0;
            int link = 0;
            for(int i = 0; i<N; i++){
                for(int j = i+1; j<N; j++){
                    if(visit[i] != visit[j]) continue;
                    if (visit[i])
                        start += player[i][j] + player[j][i];
                    else
                        link += player[i][j] + player[j][i];
                }
            }
            int diff = Math.abs(start - link);
            if(diff < result) result = diff;

            return;
        }
        visit[cnt] = true;
        solve(cnt+1);
        visit[cnt] = false;
        solve(cnt+1);
    }
}

 

 [해설]
     

 :  static int N, result;  선수, 결과
    static int[][] player;  능력치
    static boolean[] visit;  방문처리

 

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());  첫째줄 입력
    player = new int[N][N];  선수 능력치

      
    for(int i = 0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j<N; j++){
                player[i][j] = Integer.parseInt(st.nextToken());  능력치 입력받기
            }
    }

 :  result = Integer.MAX_VALUE;  결과
    visit = new boolean[N];  방문 확인
    solve(0);  0부터 체크 시작
    System.out.println(result);  결과 확인
    

 :  static void solve(int cnt){  선수들의 조합 탐색 (부분집합 찾기)
        if(cnt == N){  모든 선수를 택했을 때
            int team1 = 0;
            int team2 = 0;
            for(int i = 0; i<N; i++){  팀원을 구분하여 능력치를 합산
                for(int j = i+1; j<N; j++){같은 팀에 속한 플레이어만 능력치를 합산하며, visit 배열을 통해 팀 소속 여부를 확인
                    if(visit[i] != visit[j]) continue;  visit 배열을 통해 팀 소속 여부를 확인
                    if (visit[i])  같은 팀에 속한 선수들만 능력치를 합산
                        team1 += player[i][j] + player[j][i];
                    else
                        team2 += player[i][j] + player[j][i];
                }
            }
            int diff = Math.abs(team1 - team2);  두 팀의 능력치 차이
            if(diff < result) result = diff;  현재까지의 최소 차이(result)와 비교하여 더 작은 값을 저장
            return;

        }

        visit[cnt] = true;  현재 팀원을 첫 번째 팀에 포함 (visit = true는 첫 번째 팀)
        solve(cnt+1);  다음 팀원에 대한 팀 결정을 재귀적으로 호출 
        visit[cnt] = false;  현재 팀원을 두 번째 팀에 포함 (visit = false는 두 번째 팀)
        solve(cnt+1);  다음 팀원에 대한 팀 결정을 재귀적으로 호출 
    }
}



 

 

이제 풀어보러 갈께요 :)

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

https://www.acmicpc.net/problem/15661

15661번: 링크와 스타트