삼성 SW 역량테스트 백준 스타트와링크 15561

2021-04-21

1. 문제 링크

2. 컴퓨팅 사고

(1) N은 20까지 주어지므로 시간복잡도가 충분히 주어지므로 DFS를 통한 모든 경우를 구해주었다. 그리고 짝수인 팀원들을 구해야한다.
(2) 가장중요한점은 팀을 어떻게 분리시킬 것인가를 잘 생각해야한다. 하나의 팀을 나누는 변수를 두어 스타트팀은 true, 링크팀은 false로 두고 나누어준다. 그리고 DFS종료조건은 N/2명으로 나눌 수 있는 경우에 처리를 한다. 팀을 두개로 분리하기때문에 이와 같은 처리를 하게 되는 것이다.
(3) 조합을 사용하여 모든 경우의 수를 찾아준다. (idx변수를 선언하여 이전의값은 쳐다보지 않는다.) 문제에서 Sij, Sji를 동시에 계산하고 있으므로 같은것으로 보고 있기때문에 순열을 구할 필요가 없다.
(4) 홀수처리와 짝수처리를 따로따로 분리해야하는 것으로 착각을 하게 된 문제였다. 각 팀의 인원이 홀수가 되면 그 처리를 따로 처리를 해줄 필요가 없었다.
(5) 이제 체크된 값 True False에 따라 팀을 분리하고 True인 경우에는 스타트팀, False인 경우에는 링크팀의 능력치를 더해나가면서 팀원의 능력치의 최소를 구해주고, 음수가 나올 수 있으므로 절댓값을 처리한다.

예를 들어보면,

n=6 일 경우로 가정하고 스타트팀이 3명(1,2,3) , 링크팀이 3명(4,5,6) 이라고 가정하면

1 2	스타트팀의 능력치 = S12 + S21 + S13 + S31 + S23 + S32 링크팀의 능력치 = S45 + S54 + S46 + S64 + S56 + S65

와 같이 홀수팀으로 구성되어도 모든 능력치를 구할 수 있는것을 알 수 있다.

3. 소스 코드

package Samsung.ing;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class 링크와스타트_15561번 {
    static int[][] map;
    static int n;
    static boolean[] isChecked;
    static List<Integer> arrList;
    static int answer;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        isChecked = new boolean[n+1];
        arrList = new ArrayList<>();
        answer = Integer.MAX_VALUE;
        StringTokenizer st;
        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());
            }
        }
        dfs(0, 0);
        System.out.println("answer = " + answer);
    }

    // 조합
    private static void dfs(int idx, int cnt) {
        // == n개를 선택된 경우
        if(cnt == n/2){
            int startTeamScore = 0;
            int linkTeamScore = 0;
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(i == j) continue;
                    if(isChecked[i] && isChecked[j]){
                        startTeamScore += map[i][j];
                        System.out.println(map[i][j]);
                    }
                    else if(!isChecked[i] && !isChecked[j]) linkTeamScore += map[i][j];
                }
            }
            System.out.println("==========");
            answer = Math.min(answer, Math.abs(startTeamScore - linkTeamScore));
            return;
        }
        // == 스타트팀: true, 링크팀 false
        for(int i=idx; i<n; i++){
            if(isChecked[i]) continue;;
            isChecked[i] = true;
            dfs(i, cnt+1);
            isChecked[i] = false;
        }

    }
}

AlgorithmSW역량테스트

1. 문제 링크

2. 컴퓨팅 사고

3. 소스 코드