알고리즘 풀이 - 백준 15661(링크와 스타트, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

관련 문제인 14889번 풀이 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

N명의 인원을 2팀(스타트팀, 링크팀)으로 나누어 능력치를 계산하는 문제. 각 팀에는 1명 이상 있어야 한다.

이전 문제인 스타트와 링크는 무조건 팀을 반으로 했으나 이 문제는 두 팀의 인원이 달라도 된다.

 

 

2. 풀이

 

이 문제는 우선 N명의 사람들을 두 팀으로 나누되 최소 1명은 배정되도록 해야 한다.

우선 팀을 배정하는 작업을 수행하려면 그 경우의 수를 모두 따져봐야 하므로 완전 탐색을 통해 해결 해야 한다.

그 이후, 능력치를 계산하기 위해서 배정된 상태에서 값을 계산하기만 하면 된다. 즉, 팀을 배정 시의 완전 탐색을 어떻게 사용하느냐의 문제이다.

 

1명 이상의 경우를 모두 체크하는데, 재귀를 통한다면 재귀의 탈출 조건을 지정해야 한다!

능력치가 모두 계산이 완료된 경우, 한 팀에만 N명이 모두 배정된 경우가 탈출 조건이 될 수 있다.

 

재귀를 사용한다면 현재 함수의 상태 값 또한 중요하다. 탈출 조건에 사용하는 것이 어느 팀에 몇 명이 배정되었는지 이므로 각 팀에 배정된 인원을 저장하는 것이 중요하다.

위 내용을 코드로 정리한 것을 아래에서 확인하자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.io.*;

public class Main{
    static int n;
    static int player[];
    static int S[][];
    static int ans = Integer.MAX_VALUE;
    static int start[];
    static int link[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        player = new int[n];
        S = new int[n][n];

        for(int i=0; i < n; i++){
            String[] line = br.readLine().split(" ");
            for(int j=0; j < n; j++){
                S[i][j] = Integer.parseInt(line[j]);
            }
            player[i] = i;
        }

        start = new int[n];
        link = new int[n];

        // 재귀 방식으로 Team을 구성
        makeTeam(0, 0);

        bw.write(String.valueOf(ans));
        bw.flush();
        br.close();
    }

    private static void makeTeam(int s, int l){
        // 배정이 완료된 경우 계산 수행.
        // 만약 start 또는 link팀에 n명이 모두 배정된 경우는 계산하지 않고 넘어간다.
        // start + link 팀 배정이 n명이면 계산 후 반환한다.
        if(s >= n || l >= n) return;
        if(s + l == n){
            calc(s, l);
            return;
        }

        // start / link 팀에 각각 선수 배정(재귀)
        start[s] = player[s+l];
        makeTeam(s+1, l);

        // s = 0이라는 것은 위에서 제일 처음 이 method가 수행될 때 상단 재귀를 모두 끝내고
        // link팀 부터 배정하는 경우임.
        // 이 경우는 start 팀부터 배정하는 경우와 동일하게 반복됨. 따라서 또 할 필요가 없다.
        if(s == 0) return;

        link[l] = player[s+l];
        makeTeam(s, l+1);
    }

    private static void calc(int s, int l){
        int start_score = 0;
        int link_score = 0;

        // 배정된 인원 기반 점수 계산
        for(int i=0; i < s; i++){
            for(int j=0; j < s; j++){
                start_score += S[start[i]][start[j]];
            }
        }

        for(int i=0; i < l; i++){
            for(int j=0; j < l; j++){
                link_score += S[link[i]][link[j]];
            }
        }
        ans = Math.min(ans, Math.abs(start_score - link_score));
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.