[Baekjoon]백준 14889 스타트와 링크(실버 1) - Python

문제설명 1

문제설명 2

예제

문제를 살펴보면 각 사람들의 능력치가 표를 보고 두 개의 팀을 만들었을 때 그 능력치의 차이가 최소가 되어야한다

해결을 위한 로직을 생각해보면 모든 경우의 수를 다 해보면서 합을 구해보고, 최솟값을 찾아내야한다

이 문제는 백트래킹 단계에 속해있기 때문에 연습을 위해 백트래킹 알고리즘을 사용하여 코드를 작성해보자

 

문제에서 N과 한 칸의 최대값이 정해져있기 때문에 result값을 초기에 1000000 정도로 설정해주었다

for문을 통해 능력치를 저장할 리스트를 만들어주고, 이제부터 본격적으로 백트래킹을 사용한 코드를 작성해야한다

 

solve함수의 인자로 n을 받아 이 수가 N//2가 된다면 각각의 팀에 능력치를 저장해주어야한다

또한 start팀에 속해있지 않다면 link팀이라는 뜻이므로  solve함수의 인자로

start_team의 정보를 받아 두 개의 for문을 통해 능력치의 합을 저장해준다

두 개의 for문을 통해 start_score, link_score에 ability리스트에서 값을 가져온 값을 더해 저장하면 된다 

이후 result의 값을 result와 최솟값 중에서 더 작은 값으로 최신화해준다

다른 경우를 확인하기위해 for문을 통해 idx값부터 N까지 solve함수를 반복해주면 된다

def solve(n, idx, start_team):
    global result
    if n == N//2:
        link_team = []
        for i in range(N):
            if i not in start_team:
                link_team.append(i)
                
        start_score, link_score = 0, 0
        for i in start_team:
            for j in start_team:
                start_score += ability[i][j]
        for i in link_team:
            for j in link_team:
                link_score += ability[i][j]
                
        result = min(result, abs(start_score - link_score))
        return
    
    for i in range(idx, N):
        solve(n + 1, i + 1, start_team + [i])
        

N = int(input())
ability = []
for _ in range(N):
    soccer = list(map(int, input().split()))
    ability.append(soccer)
    
result = 1000000

solve(0, 0, [])
print(result)

백트래킹 문제는 풀때마다 헷갈리는 요소가 많아서 고민을 오래 하게 되는 것 같다 앞으로도 꾸준히 풀어봐야겠다