1. 문제 링크 및 문제
https://www.acmicpc.net/problem/14889
1-1 문제 요약
: N*N의 배열에서 N/2 의 명으로 이루어진 2개의 팀으로 나뉨.
(array[i][j] + array[j][i]) - (array[x][y]+array[y][x]) 의 값이 (i,j,x,y 는 다 다른 수) 최솟값인 경우
2. 해결 방법 생각해보자 ...
팀 내부 인원을 변경하며 모든 경우 탐색 = 백트래킹 방법
1. 팀을 나눔. visited 로 구분
2. count 로 인원확인, count == N/2 일 때 능력치 계산
3. 코드
N = int(input())
arr = [list(map(int ,input().split())) for _ in range(N)]
visited = [False]* N
MinAns = int(1e9)
def dfs(count,idx):
global MinAns
if count == N/2 :
Ateam, Bteam = 0,0
for i in range(N):
for j in range(i+1,N):
if visited[i] and visited[j]:
Ateam += (arr[i][j] + arr[j][i])
elif not visited[i] and not visited[j]:
Bteam += (arr[i][j] + arr[j][i])
MinAns = min(MinAns,abs(Ateam-Bteam))
return
for i in range(idx,N):
if not visited[i] :
visited[i] = True
dfs(count+1, i+1)
visited[i] = False
dfs(0,0)
print(MinAns)! 놓친 점
시간초과.
반복문 조건을 계속 수정하여 겨우 맞았다 ... !
포스팅 작성 할 때 두 번 풀어보고 작성하는데 얘는 두번으로 안되겠다
이 문제는 다른 분들 코드도 참고하여 세번이고 네번이고 더 풀려고 다음주 to-do list 에 추가해둠 ..
더 좋은 풀이방법을 내것으로 만들게 된다면 게시글 수정해야지!
