https://www.acmicpc.net/problem/14889
문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.
BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.
N=4이고, S가 아래와 같은 경우를 살펴보자.
|i\j |1|2|3| | :- | :- | :- | :- | |4| |5|6| |7|1| |2| |3|4|5| | 예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.
- 스타트 팀: S12 + S21 = 1 + 4 = 5
- 링크 팀: S34 + S43 = 2 + 5 = 7
1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.
- 스타트 팀: S13 + S31 = 2 + 7 = 9
- 링크 팀: S24 + S42 = 6 + 4 = 10
축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.
백트레킹 문제의 결정적인 것은 결정하는 탐색 과정을 줄여나간다는 것에 있다. 브루트포스(완전탐색)와 비슷한 면이 있지만 말그대로 차이점은 탐색 과정(결정트리)을 보면 된다는데
예를 들어서 이번 문제에서 1,2,3,4 사람이 있다고 했을때 여러 조합이 있을 수 있다.
(1,2) (1,3) (1,4) (2,3) (2,4) (3,4) 하지만 여기서 내가 만약 (1,2) 조합을 골랐다고 하자.
그러면 자동으로 다른 선택지는 사라지고 (3,4)만 남게되고 결국 (1,2)와 (3,4)를 비교하는 것으로 남는다.
재귀를 적절하게 이용을 해서 (마지막 결정 순간) 살펴보면 되지 않을까 하는 생각은 있지만. 역시 어렵다.
이 속도로 수요일까지 남은 문제는 다 풀수 있나 모르겠다. 볼거 태산인데 하… 비록 시간이 없어서 많은 고민을 하고 직접 풀지는 못하지만 최대한 한 문제라도 이해하고 머리에 담아가겠다는 생각으로 움직여야 겠습니다.
1
2
3
4
5
6
7
n = int(input())
team_point = []
for i in range(n):
team_point.append(list(map(int,input().split())))
start = []
link = []
먼저 입력 받는 부분입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def dfs(idx):
global minans
if idx==n//2:
start_team =0
link_team = 0
for i in range(0,n):
if i not in start:
link.append(i)
for i in range(0,n//2-1):
for j in range(i+1,n//2):
start_team += team_point[start[i]][start[j]]+team_point[start[j]][start[i]]
link_team +=team_point[link[i]][link[j]]+team_point[link[j]][link[i]]
diff =abs(start_team-link_team)
minans = min(minans, diff)
link.clear()
return
for i in range(n):
if i in start:
continue
if len(start) >0 and start[len(start)-1] > i:
continue
start.append(i)
dfs(idx+1)
start.pop()
DFS와 백트래킹인데 일단 천천히 봅시다. 먼저 인덱스가 n//2일때에만 작동하는 것은 나중에 보고 먼저 밑에서 for문이 도는 것부터 봅시다.
1
2
3
4
5
6
7
8
for i in range(n):
if i in start:
continue
if len(start) > 0 and start[len(start)-1] > i:
continue
start.append(i)
dfs(idx+1)
start.pop()
일단 start와 link는 초기화 되었기에 아무것도 없습니다. start는 현재 비어있고 len(start)도 당연히 0입니다.
start에 i를 집어넣고 재귀로 들어갑니다. n이 4일때 예시로 진행을 하겠습니다. 인덱스는 아직 1이기 때문에 한번더 재귀를 들어갑시다. 이제 idx조건이 만족했으니 처음에 가지 못했던 조건문으로 들어가봅시다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
if idx==n//2:
start_team = 0
link_team = 0
for i in range(0,n):
if i not in start:
link.append(i)
for i in range(0,n//2-1):
for j in range(i+1,n//2):
start_team += team_point[start[i]][start[j]]+team_point[start[j]][start[i]]
link_team +=team_point[link[i]][link[j]]+team_point[link[j]][link[i]]
diff =abs(start_team-link_team)
minans = min(minans, diff)
link.clear()
return
start_team과 link_team은 0으로 초기화를 하고 순회를 해봅시다.
일단 start는 0과 1이 들어가 있는 상황입니다. 첫번째 for문에서 link는 start에 들어 있지 않은 2,3이 들어가게 됩니다.
그 다음 for문을 봅시다. 이중 for문으로 돌아가게 되는데 i와 j가 순회하는 곳은 예시의 n을 4라고 했으니
i의 범위는 0부터 1까지 j는 i+1 = 1부터 2까지 즉 i는 0한번만 j 역시 1한번만 나오게 됩니다.
그리고 각 팀의 합을 구하고 절대 크기 차이를 비교해서 다 작은 값이 있다면 갱신을 해 나갑니다.
start를 찍어보면 위 처럼 각 조건을 만족할때까지 담게되고
각 사람의 조합의 수가 모두 나오게 됩니다. 아니면 재귀로 푸는 대신 combination 함수를 사용해서 모든 경우의 수를 뽑아서 순회 시키는 방법도 존재할거 같습니다.
Comments powered by Disqus.