백준 삼성 코딩 기출 문제 - 스타트와 링크 python

백준 삼성 코딩 기출 문제 - 스타트와 링크 python

출처 : BAEKJOON ONLINE JUDGE

스타트와 링크 (https://www.acmicpc.net/problem/14889)

문제 설명

축구를 하기 위해 짝수인 N명이 모여 N/2명으로 팀을 구성하려고 합니다. 이 문제는 2개의 팀(스타트, 링크팀)의 능력치 차이의 최소값을 출력하는 문제입니다. 능력치를 계산하는 방법은 팀원들끼리 주어진 배열에서 row 인덱스인 i와 column 인덱스의 j를 서로 맞바꿔 값을 더합니다.

문제 풀이

재귀 함수로 구현합니다

[1] 입력을 받습니다.

n = int(input()) team = [list(map(int, input().split())) for _ in range(n)]

[2] 스타트 팀과 링크팀을 구분하기 위해 myteam이라는 배열을 사용합니다. 능력치 차이 값은 answer로 초기화합니다. True -> 스타트팀, False -> 링크팀으로 정의합니다.

myteam = [False] * n # 팀을 구분한다. True-> 스타트팀, False->링크팀 answer = 1e9

[3] 재귀 함수로 구현합니다.

 - 전체 N명에 대해서 확인이 끝났다면 종료 합니다.

 - 팀원이 N/2명으로 떨어진다면 각 스타트팀과 링크팀의 능력치를 계산합니다.

 - 능력치를 계산할 때는 스타트팀은 True, 링크팀은 False로 조건에서 확인하고 각 팀에 능력치를 합산합니다.

 - 두 팀의 능력치 차이가 최소가 되도록, 빼버린 값에 abs 절대값을 넣고 최소를 비교하여 저장합니다.

 - 재귀 함수는 스타트팀인 경우와 링크팀에 대해서 호출합니다.

def solve(count, index):     global answer         if index == n: # 전체 N명에 대해서 확인이 끝났다면 종료         return     if count == n//2: # 팀원이 N/2로 떨어진다면,         s_team, link_team = 0, 0 #  스타트팀, 링크팀         for i in range(n):             for j in range(n):                 if myteam[i] and myteam[j]: # 스타트팀                     s_team += team[i][j] # 능력치를 구한다.                 if not myteam[i] and not myteam[j]: # 링크팀                     link_team += team[i][j]         answer = min(answer, abs(s_team - link_team)) # 두 팀의 능력치 차이가 최소가 되는 값         return         myteam[index] = True # 스타트팀     solve(count+1, index+1)     myteam[index] = False # 링크팀     solve(count, index+1)

[4] 최종적으로 호출하고 결과를 출력합니다.

solve(0, 0) print(answer)

전체 코드

n = int(input()) team = [list(map(int, input().split())) for _ in range(n)] myteam = [False] * n # 팀을 구분한다. True-> 스타트팀, False->링크팀 answer = 1e9 def solve(count, index):     global answer         if index == n: # 전체 N명에 대해서 확인이 끝났다면 종료         return     if count == n//2:         s_team, link_team = 0, 0 #  스타트팀, 링크팀         for i in range(n):             for j in range(n):                 if myteam[i] and myteam[j]: # 스타트팀                     s_team += team[i][j] # 능력치를 구한다.                 if not myteam[i] and not myteam[j]: # 링크팀                     link_team += team[i][j]         answer = min(answer, abs(s_team - link_team)) # 두 팀의 능력치 차이가 최소가 되는 값         return         myteam[index] = True # 스타트팀     solve(count+1, index+1)     myteam[index] = False # 링크팀     solve(count, index+1) solve(0, 0) print(answer)