(JAVA) 백준 14889번 : 스타트와 링크

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

14889번: 스타트와 링크

 

 

어렵지 않은 브루트 포스 문제.

 

삼성 SW 코딩 테스트 기출문제

 

 

백트래킹을 사용했음.

 

 

 

 

핵심을 간단히 말하자면

 

 

1) N명이 있으면, 절반으로 나눠 두 팀을 만든다. 

boolean[] 배열을 사용해 True / False 로 팀을 구분하면 된다.

 

 

2) 팀 내 능력치 차이의 최소를 구하고,

같은 팀 내 사람들끼리 능력치를 계산하므로

팀을 꼭 구분지을 필요가 없다.

 

 

즉,

 

N = 4일 때

 

스타트 팀    |     링크 팀

1)  1, 3                2, 4

2)  2, 4                1, 3

 

 

이렇게 구분지을 필요 없이 둘 다 같은 결과값을 출력한다.

 

 

 

 

매커니즘도 간단하다.

 

 

매커니즘

---

1) int[][] 배열 map에 입력 값 능력치 저장.

 

2) 백트래킹 시작

*** 이 때 팀을 구분지을 필요가 없기 때문에 boolean 배열의 첫 번째는 True로 놓고 2번 째 인덱스부터 백트래킹을 시작한다.

 

 

3) 백트래킹을 통해 구한 boolean 배열을 가지고 x, x + 1 두 원소 값 비교.

이 때, 같은 boolean 값을 가질 경우 같은 팀이므로 map[x][y] + map[y][x] 를 누적 저장한다.

*** 값이 같을 때 이 값이 True인지 False인지 구분해서 각각 누적값을 따로 저장해야 한다.

 

 

4) 가장 최소가 되는 결과 값 출력.

 

 

 

 

 

쉽죠 ?!

 

삼성 화이팅합시다.

 

 

감사합니다!

 

 

소스코드

---