[백준 알고리즘, 브루트 포스] 삼성 SW 역량 테스트 문제 :: 14889번 스타트와 링크

이번에도 삼성 코딩테스트, 삼성 SW 역량 테스트 문제 풀이!!

풀어보고 싶으신 분은 아래의 링크를 참조해주세요!

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

14889번: 스타트와 링크

 

이번 14889번 스타트와 링크 문제는 생각보다 되게 간단했어요

문제를 읽어보면 아시겠지만 모든 경우를 탐색(브루트 포스BF)를 통해서

가장 작은 값을 찾는 문제에요

 

우선 팀이 나눠질 수 있는 경우를 Combination함수를 통해서 구하면 되요.

이는 백트레킹을 이용하면 더 빠르게 풀 수 있어요

그때 각각 스탯을 모두 구해서 더해주면 끝이에요!!

이는 간단하게 해결하기 위해서 매 경우마다 구한 스탯을 arraylist에 저장했어요

그리고 collection framework를 모든 스탯을 저장한 arraylist에서 최소값을 찾았어요

 

스탯은 1,2가 같은 팀이라면 1-2, 2-1의 스탯을 모두 더해주어야 되므로

4팀이 있다면 (1,2), (1,3), (1,4) (2,3), (2,4), (3,4) 이렇게 차례대로 더해주고

(4,3), (4,2), (4,1), (3,2), (3,1), (2,1) 이렇게 반대로 더해주는 식으로 계산했어요

자세한 것은 아래 자바(java) 코드를 참고해주세요!!

 

간단한 코드 설명을 덧 붙이자면

우선 입력 받은 값들을 변수에 저장시켜주고

combination 함수를 호출해요. 그리고 모든 경우의 수를 찾아가요

이때 조합은 두팀으로 나누는데 팀의 인원수는 똑같으니까 총 인원수의 절반만큼 조합을 뽑았어요

그리고 calculate함수로 들어가 뽑은 팀인 true팀과 안 뽑은 팀인 false팀으로 나누어서

능력치를 계산해주었어요. 그리고 둘의 차이의 절댓값을 Math의 abs함수로 구해주어서 저장

이렇게 해서 마지막에 collections를 이용해 출력해주었답니다!!

 

---

백준 14889번 스타트와 링크 자바 풀이

---

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Main {
	static ArrayList<Integer> sum_statList;

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int totalNum = scan.nextInt();
		int[][] allStat = new int[totalNum][totalNum];
		boolean[] visited = new boolean[totalNum];
		
		sum_statList = new ArrayList<Integer>();
		
		for(int i=0; i<totalNum; i++){
			for(int j=0; j<totalNum; j++){
				int temp = scan.nextInt();
				allStat[i][j] = temp;
			}
		}

		combination(allStat, visited, 0, totalNum, totalNum/2);
		System.out.println(Collections.min(sum_statList));

	}

	private static void combination(int[][] arr, boolean[] visited, int start, int N, int r){
		if(r==0){
			sum_statList.add(calculateStat(arr, visited, N));
		}
		else{
			for(int i=start; i<N; i++){
				visited[i] = true;
				combination(arr, visited, i+1, N, r-1);
				visited[i] = false;
			}
		}
	}

	private static int calculateStat(int[][] arr, boolean[] visited, int N){
		int sumStartTeam = 0;
		int sumLinkTeam = 0;
		
		ArrayList<Integer> startTeam = new ArrayList<Integer>();
		ArrayList<Integer> linkTeam = new ArrayList<Integer>();
		
		// 팀 나누기
		for(int i=0; i<N; i++) {
			if(visited[i])
				startTeam.add(i);
			else
				linkTeam.add(i);
		}
		
        // (1,2,3)이 팀인 경우
        // 1-2, 1-3, 2-3 스탯 더하기
		for(int i=0; i<startTeam.size(); i++) {
			for(int j=i+1; j<startTeam.size(); j++) {
				sumStartTeam += arr[startTeam.get(i)][startTeam.get(j)];
				sumLinkTeam += arr[linkTeam.get(i)][linkTeam.get(j)];
			}
		}
		
        // (1,2,3)이 팀인 경우 위와 반대의 경우 구하기
        // 3-2, 3-1, 2-1 스탯 더하기
		for(int i=startTeam.size()-1; i>0; i--) {
			for(int j=i-1; j>=0; j--) {
				sumStartTeam += arr[startTeam.get(i)][startTeam.get(j)];
				sumLinkTeam += arr[linkTeam.get(i)][linkTeam.get(j)];
			}
		}
		
		return Math.abs(sumStartTeam - sumLinkTeam);
	}
}

 

이해 안가시는 부분은 댓글 달아주세요

도움이 되셨다면 하트 꾸욱 클릭 부탁드립니다!!

2019/10/11 - [알고리즘/백준 알고리즘] - [백준 알고리즘, 브루트 포스] 삼성 SW 역량 테스트 문제 :: 13458번 시험감독

2019/10/09 - [알고리즘/백준 알고리즘] - [백준 알고리즘, 백트레킹, 브루트 포스] 삼성 SW 역량 테스트 문제 :: 14502번 연구소

2019/10/10 - [언어/자바(JAVA)] - [자바(JAVA)] ArrayList, Map의 최소값 구하기 (collection framework)