[백준] 스타트와 링크

문제

https://www.acmicpc.net/problem/14889

TC

O(N^2)

Idea

조합 라이브러리를 사용한 풀이와, DFS 풀이 두 가지로 풀어보았다.
풀이는 다르지만, 해결한 아이디어는 동일하다.

라이브러리를 사용해서 n//2 명의 start 팀원을 구하고 전체 멤버에서 start 팀원을 제외하면 link 팀원을 만들 수 있다.

두 개의 팀으로 나뉜 각각의 팀에서 2명씩 랜덤하게 뽑으며 능력치를 더해주는 방식으로 풀면 해결할 수 있다.

조심해야 될 점은 list 끼리의 '-' 연산은 안 된다는 것!
set 끼리의 연산은 가능하기 때문에 set으로 바꿔서 link 팀원을 구한 후, list로 반환해주면 된다.

code (Python)

combinations 풀이

from itertools import combinations

# 입력 값
n = int(input())
# 능력치
graph = [list(map(int, input().split())) for _ in range(n)]
members = [i for i in range(n)]

# 능력치의 차이가 가장 작은 값
result = int(1e9)

# 랜덤으로 n//2명씩 팀 짜기
for r1 in combinations(members, n//2):
    r2 = list(set(members) - set(r1))
    # 스타트 팀, 링크 팀 점수 초기화
    start, link = 0, 0
    # r1팀에서 2명씩 랜덤으로 뽑으며 능력치 더해주기
    for r in combinations(r1, 2):
        start += graph[r[0]][r[1]]
        start += graph[r[1]][r[0]]
    # r2팀에서 2명씩 랜덤으로 뽑으며 능력치 더해주기
    for r in combinations(r2, 2):
        link += graph[r[0]][r[1]]
        link += graph[r[1]][r[0]]

    # 결과값은 기존 값과 두 능력치의 차이 중 더 작은 값으로 갱신
    result = min(result, abs(start - link))

print(result)

DFS 풀이

def dfs(depth, idx):
    global result
    # n//2명씩 팀이 구성 됐으면
    if depth == n//2:
        # 스타트 팀 능력치 초기화
        start, link = 0, 0
        for i in range(n):
            for j in range(n):
                # 둘 다 true 값이라면 둘이 한 팀
                if visited[i] and visited[j]:
                    start += graph[i][j]
                # 둘 다 false 값이라면 둘이 한 팀
                elif not visited[i] and not visited[j]:
                    link += graph[i][j]
        # 능력치 차이의 최솟값 갱신
        result = min(result, abs(start - link))
        return

    for i in range(idx, n):
        if not visited[i]:
            visited[i] = True
            dfs(depth+1, i+1)
            visited[i] = False

# 입력 값
n = int(input())
# 능력치
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [False for _ in range(n)]

# 두 팀의 능력치의 차이의 최소값
result = int(1e9)
dfs(0, 0)

print(result)

self code review

최대한 라이브러리를 안 쓰고 DFS 연습을 하기 위해 두 가지 방법으로 풀어보았다.

비슷하지만 시간 복잡도를 비교해보면 조합 라이브러리 < DFS 인 듯하다.
아무래도 라이브러리를 사용하는 편이 입력 값이 작을 때에는 더 효율적인가 보다.

하지만, 라이브러리 사용이 불가한 곳이나 (삼성 역테!!) 경우에 따라 DFS를 사용해야 하는 경우도 있을테니, 두 가지 풀이 방법을 다 알아두는 편이 좋다.