[백준] 14889번 : 스타트와 링크 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

14889번: 스타트와 링크

 

1. 문제 설명

2. 풀이과정

해당 문제는 모든 인원을 정확하게 두 팀으로 나누고 나눈 두 팀의 능력치를 계산하여 그 차이의 최솟값을 구하는 문제이다.

팀을 정확하게 두 팀으로 나누어야 하고, 나눈 두 팀에 대해 각 능력치를 구한 뒤, 두 팀의 능력치의 차이를 계산해야 한다. 계산한 능력치의 차이 중 최솟값을 구하면 된다.

하여 제일 앞사람부터 첫 번째 팀으로 이동하며 팀을 나눈다.

만약 첫 번째 팀의 인원이 전체 인원의 절반이 되면, 남은 사람들은 모두 두 번째 팀이 된다.

두 팀으로 나누어졌으면 각 팀원들이 같은 팀이 되었을 때 더해지는 능력치를 계산하여 각 팀별 최종 능력치를 구한다.

구한 팀별 능력치의 차이를 계산해 현재 최솟값과 비교하여 더 작은 값을 저장한다.

해당 경우에 따른 계산이 끝나면 첫 번째 팀에 넣은 인원을 제거하여 팀 구성을 새롭게 한다. (백트랙킹 활용)

가능한 모든 팀 구성별 능력치의 차이를 확인해 최종 최솟값을 구한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 인원수를 입력받는다. N = int(sys.stdin.readline())
3. 각 사람별 팀이 되었을 때 팀에 더해지는 능력치를 저장할 리스트를 생성한다. S = list()
4. 인원수만큼 반복하며 for _ in range(N)
5. 능력치 표의 값을 입력받아 리스트로 추가한다. S.append(list(map(int, sys.stdin.readline().split())))
6. 나누어진 두 팀의 최종 능력치를 구할 함수를 정의한다. def colPower()
7. 첫 번째 팀의 능력치를 저장할 변수를 생성하고 초기화한다. power1 = 0
8. 첫 번째 팀의 팀원을 한 명씩 두 명 불러 for i in team1: for j in team1
9. 두 팀원으로 인해 더해지는 능력치를 최종 팀 능력치에 더한다. power1 += S[i][j]
10. 두 번째 팀의 능력치를 저장할 변수를 생성하고 초기화한다. power2 = 0
11. 두 번째 팀의 팀원을 한 명씩 두 명 불러 for i in team2: for j in team2
12. 두 팀원으로 인해 더해지는 능력치를 최종 팀 능력치에 더한다. power2 += S[i][j]
13. 두 팀의 최종 능력치의 차이를 반환한다. return abs(power1 - power2)
14. 두 팀으로 나누고 최종 능력치 차이 중 최솟값을 구할 함수를 정의한다. def solution(n)
15. 두 팀의 최종 능력치의 차이 중  최솟값을 저장할 변수를 외부에서 불러온다. global MIN
16. 만약 첫 번째 팀의 인원수가 전체 인원수의 절반이 되면 if (len(team1) == N // 2)
17. 두 번째 팀을 저장할 리스트를 초기화한다. team2.clear()
18. 모든 사람을 한 명씩 불러 for i in range(N)
19. 만약 해당 사람이 첫 번째 팀에 없다면 if (i not in team1)
20. 두 번째 팀에 추가한다. team2.append(i)
21. 정확히 두 팀으로 나눈 후, 각 팀의 최종 능력치의 차이를 구해 현재 최솟값과 비교하여 최솟값을 저장한다. MIN = min(MIN, calPower())
22. 현재 경우에 따른 최솟값을 비교하였으므로 종료한다. return
23. 반면 아직 팀이 나누어지지 않았다면 현재 남은 인원 중 앞사람부터 for i in range(n, N)
24. 첫 번째 팀으로 이동한다. team1.append(i)
25. 남은 다음 사람을 팀으로 나누기 위해 다음 사람을 인수로 주어 함수를 호출한다. solution(i + 1)
26. 해당 경우에 따른 결과를 모두 구했다면 현재 경우에서 첫 번째 팀으로 넣은 사람을 제거한다. team1.pop()
27. 각 팀의 인원을 저장할 리스트를 생성한다. team1 = list()  team2 = list()
28. 두 팀의 최종 능력치의 차이 최솟값을 저장할 변수를 생성하고 가능한 제일 큰 값인 100을 저장한다. MIN = 100
29. 제일 앞사람부터 팀을 나누기 위해 0을 인수로 하여 팀을 나눌 함수를 호출한다. solution(0)
30. 가능한 모든 경우에 대해 최종 능력치의 차이 중 최솟값을 출력한다. print(MIN)

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())

S = list()
for i in range(N):
    S.append(list(map(int, sys.stdin.readline().split())))

def calPower():
    power1 = 0
    for i in team1:
        for j in team1:
            power1 += S[i][j]

    power2 = 0
    for i in team2:
        for j in team2:
            power2 += S[i][j]

    return abs(power1 - power2)

def solution(n):
    global MIN

    if (len(team1) == N // 2):
        team2.clear()
        for i in range(N):
            if (i not in team1):
                team2.append(i)

        MIN = min(MIN, calPower())
        return
    
    for i in range(n, N):
        team1.append(i)
        solution(i + 1)
        team1.pop()

team1 = list()
team2 = list()

MIN = 100
solution(0)
print(MIN)