문제 : https://www.acmicpc.net/problem/14889
초기 구상과정
DFS문제라는 사실을 알고 풀기 시작했는데 case를 어떻게 나눠야할지 떠오르지 않아서 고민을 많이 했다. 단순하게 생각하자고 맘먹으니 사람의 팀 배정 case로 나누면 되겠다고 떠오름!
1. DFS / 재귀호출방식
2. 종료조건은 A팀과 B팀 list의 길이로 만들면 되겠다
len(A) or len(B) = N // 2
3. for문을 이용해서 A : 1, B : 0으로 정하고 풀기 시작
4. 종료조건을 만족했을 때 차이를 구하는 코드를 짜면 되겠다.
초기 코드 : DFS함수
def dfs(step):
global mini
if len(A) == N >> 1:
totalA = totalB = 0
for P1 in all:
for P2 in all:
if P1 in A and P2 in A and P1 != P2:
totalA += S[P1 - 1][P2 - 1] + S[P2 - 1][P1 - 1]
elif P1 not in A and P2 not in A and P1 != P2:
totalB += S[P1 - 1][P2 - 1] + S[P2 - 1][P1 - 1]
if abs(totalA - totalB) < mini:
mini = abs(totalA - totalB)
return
elif len(B) == N >> 1:
totalA = totalB = 0
for P1 in all:
for P2 in all:
if P1 in B and P2 in B and P1 != P2:
totalB += S[P1 - 1][P2 - 1] + S[P2 - 1][P1 - 1]
elif P1 not in B and P2 not in B and P1 != P2:
totalA += S[P1 - 1][P2 - 1] + S[P2 - 1][P1 - 1]
if abs(totalA - totalB) < mini:
mini = abs(totalA - totalB)
return
else:
for i in range(2):
if i:
A.append(step)
dfs(step + 1)
A.pop()
else:
B.append(step)
dfs(step + 1)
B.pop()함수를 이렇게 만들어서 돌렸더니 sample에서 정답과 다르게 나왔다. 전부 2배 값이 나와서 코드를 살펴보니 각 합계에서 전부 중복으로 2번씩 합산되게 만들어져있는 점을 수정했다.
totalA += S[P1 -1][P2 - 1]
totalB += S[P1 -1][P2 - 1] 이 코드를 제출했는데 시간초과..
수업에서 교수님께서 list에 적용되는 in은 시간 복잡도가 O(n^2)이라서 결국 for문을 쓰는 것과 같다고 알려주신 부분이 생각나서 이 코드는 결국 4중 for문을 쓴거라는 판단이 들었다.(솔직히 끔찍했다...)
최종 코드
N = int(sys.stdin.readline())
S = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dfs(step):
global mini
if len(A) == N >> 1:
totalA = totalB = 0
tmp_B = []
for player in all:
if player not in A:
tmp_B.append(player)
for i in range(N >> 1):
for j in range(N >> 1):
totalA += S[A[i] - 1][A[j] - 1]
totalB += S[tmp_B[i] - 1][tmp_B[j] - 1]
if abs(totalA - totalB) < mini:
mini = abs(totalA - totalB)
return
elif len(B) == N >> 1:
totalA = totalB = 0
tmp_A =[]
for player in all:
if player not in B:
tmp_A.append(player)
for i in range(N >> 1):
for j in range(N >> 1):
totalB += S[B[i] - 1][B[j] - 1]
totalA += S[tmp_A[i] - 1][tmp_A[j] - 1]
if abs(totalA - totalB) < mini:
mini = abs(totalA - totalB)
return
else:
for i in range(2):
if i:
A.append(step)
dfs(step + 1)
A.pop()
else:
B.append(step)
dfs(step + 1)
B.pop()
A = []
B = []
all = list(range(1, N + 1))
mini = 99 * N
dfs(1)
print(mini)4중 for문을 제외하고 새로운 방법을 찾아서 고민해서 만들었는데 그래도 조금 찝찝한 코드를 작성했다. 이중 for문을 2개 배치해서 문제되는 코드를 대체하는 방법을 썼는데 이것 역시 좋아보이지 않는다. 제출해서 시간 초과가 뜰 것도 어느 정도 예상했는데 통과는 되었다. 다만 시간이 6496ms..
개선해야할 점
당연히 실행시간에 대한 이슈이다. 최대한 내장 함수를 안쓰고 직접 구현해서 만들려고 하니 코드길이가 늘어나는 부분은 어쩔 수 없다고 생각하는데 실행시간이 이건 길어도 너무 긴 문제가 있다고 생각되어 더 찾아보고 공부해서 다른 방법이 없는지 알아봐야겠다. 숙제를 했다고 생각했는데 숙제가 더 늘었다.
