[BOJ / 파이썬] 14889: 스타트와 링크

백준 / BOJ / Python / 파이썬

문제 링크 : https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

단계 : 백트래킹

알고리즘 분류 : 브루트포스 알고리즘, 백트래킹 

 

풀이:

두 팀 간의 전력 차이를 최소화해야 한다. 사람 수, 사람들의 능력치를 입력받는다.

 

team이라는 리스트를 만들 것이다. 이 리스트에 들어있는 사람들은 start팀으로 간주할 것이고 이 리스트에 들어있지 않은 사람들은 link 팀으로 간주할 것이다.

 

solve의 인자를 순서대로 설명하면 n은 팀 배정이 완료됐는지 확인하기 위한 수이고 s는 현재 마지막으로 팀에 들어간 (선수의 번호 -1)이다. n을 2씩 더하는 이유는 한 팀 count의 반까지만 들어갈 수 있으니 팀 배정이 완료 됐을 때 count와 같게 하기 위해 2씩 더했다. n을 1씩 더하고 싶으면 if문의 n == count가 아니라 n == count//2로 하면 된다.

 

solve 함수의 else 부분을 보면 먼저 선수들을 팀에 배정한다. 0번 선수부터 끝번 선수까지 번호를 돌아가며 현재 for문으로 들고 있는 번호의 선수가 start팀에 없다면 team 리스트에 넣어주고 그 다음 번호를 n 자리에 넣어준 후 solve함수를 재귀로 호출해준다. 그런식으로 각 팀에 선수가 모두 배정이 될 때까지 재귀가 완료되어 n == count라는 조건이 완료되면 문제의 조건에 따라 각 팀의 능력치를 구한다. 이중 for문을 통해 team 리스트에 있는 선수끼리는 start팀의 능력치에 더하고 team 리스트에 없는 선수끼리는 link 팀에 능력치를 더해준다. 양 팀의 능력치 총합을 구하면 둘의 차를 res 리스트에 저장해준다.

 

재귀가 완료되어 나오면 for문을 통해 진행할 다음 경우의 수를 위해 team 리스트에서 방금 넣었던 선수를 제거해준다. 그렇게 모든 경우의 수를 찾고 모든 능력치 총합의 차를 구하면 그 중 가장 차가 작은 값을 출력하기 위해 min() 함수를 이용한다.

 

14888: 연산자 끼워넣기에 이은 "삼성 SW 역량 테스트 기출 문제 2"라고 한다. 화이팅

 

코드

import sys


def solve(n, s, count):
    global team, res
    if n == count:
        start = 0
        link = 0
        for i in range(count):
            for j in range(count):
                if i in team and j in team:
                    start += ls[i][j]
                elif i not in team and j not in team:
                    link += ls[i][j]
        res.append(abs(start - link))
    else:
        for i in range(s, count):  # 배열 편의상 선수 번호 -1
            if i not in team:
                team.append(i)
                solve(n + 2, i, count)
                team.remove(i)


people = int(sys.stdin.readline())
ls = []
for i in range(people):
    ls.append(list(map(int, sys.stdin.readline().split())))
team = []
res = []

solve(0, 0, people)
print(min(res))