[백준] 14889번 / Java, Python
Baekjoon Online Judge
algorithm practice
단계별 문제풀기
13. 백트래킹
모든 경우를 탐색하는 백트래킹 알고리즘을 배워 봅시다.
모든 경우를 탐색하는 백트래킹 알고리즘을 배워 봅시다.
Java / Python
8. 스타트와 링크
삼성 SW 역량 테스트 기출 문제 2
이 문제의 경우 설명이 복잡해 보여 이해가 어려워보입니다만,
간단히 중요한 점을 정리하면, 두 팀으로 나누는데, 각 팀의 능력치 차이를 최소화 한다는 것입니다.
즉, 팀의 전력차가 적게 나도록 팀을 구성하도록 하면 되는 것 같습니다.
모든 조합의 경우의 수를 탐색하여 두 팀의 능력치가 최소가 되는 수를 찾고 출력하면 되는 것 같습니다.
- Java
import java.util.Scanner;
public class Main {
static int N;
static int[][] map;
static boolean[] visit;
static int Min = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
map = new int[N][N];
visit = new boolean[N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
map[i][j] = sc.nextInt();
}
}
combi(0, 0);
System.out.println(Min);
sc.close();
}
static void combi(int idx, int count) {
// 팀 조합이 완성될 경우
if(count == N / 2) {
diff();
return;
}
for(int i = idx; i < N; i++) {
if(!visit[i]) { // 방문 안한 경우
visit[i] = true; // 방문으로 변경
combi(i + 1, count + 1); // 재귀 호출
visit[i] = false; // 재귀가 끝나면 비방문으로 변경
}
}
}
// 능력치 차 계산 함수
static void diff() {
// 방문한 팀과 방문하지 않은 팀을 각각 나누어 각 팀의 점수를 구한 뒤 최솟값을 찾는다.
int team_start = 0;
int team_link = 0;
int val = 0;
for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {
if (visit[i] == true && visit[j] == true) {
team_start += map[i][j];
team_start += map[j][i];
}else if (visit[i] == false && visit[j] == false) {
team_link += map[i][j];
team_link += map[j][i];
}
}
}
val = Math.abs(team_start - team_link);
// 두 팀의 점수차 = 0 = 가장 낮은 최솟값 = 더이상의 탐색 필요X, 0을 출력, 종료
if (val == 0) {
System.out.println(val);
System.exit(0);
}
Min = Math.min(val, Min);
}
}
- Python
from itertools import combinations
N = int(input())
board = []
for _ in range(N):
board.append(list(map(int, input().split())))
num_list = [i for i in range(N)]
res = float('inf')
def solve():
global res
# 조합을 이용하여 각 후보자를 생성함
for cand in combinations(num_list, N // 2):
# 선택된 후보와 나머지
start_member = list(cand)
link_member = list(set(num_list) - set(cand))
# 점수 비교 2명씩
start_combi = list(combinations(start_member, 2))
link_combi = list(combinations(link_member, 2))
# 점수 구하기
team_start = 0
for x, y in start_combi:
team_start += (board[x][y] + board[y][x])
team_link = 0
for x, y in link_combi:
team_link += (board[x][y] + board[y][x])
if(res > abs(team_start - team_link)):
res = abs(team_start - team_link)
solve()
print(res)
Author And Source
이 문제에 관하여([백준] 14889번 / Java, Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jini_eun/백준-14889번-Java-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)