[백준/14889] 스타크와 링크 (with 파이썬)

✔ 문제

---

✔ 풀이

😭 코드1

# https://www.acmicpc.net/problem/14889
import sys
input = sys.stdin.readline

def dfs(idx):
    global res

    if idx == n // 2: # 반은 st에 반은 li에 들어가기 때문에 n//2일때 검사
        s_res, l_res = 0, 0
        for i in range(0, n): 
            if i not in st: # st에 포함되지 않은 인원은 li에 배치
                li.append(i)
        for i in range(0, n // 2 - 1):
            for j in range(i+1, n // 2):
                s_res += arr[st[i]][st[j]] + arr[st[j]][st[i]]
                l_res += arr[li[i]][li[j]] + arr[li[j]][li[i]]

        char = abs(s_res - l_res)
        if res > char:
            res = char
        li.clear() # 계산 후 초기화
        return

    for i in range(n):
        if i in st:
            continue
        if len(st) > 0 and st[len(st) - 1] > i:
            continue
        st.append(i)
        dfs(idx + 1)
        st.pop()

n = int(input())
arr = []
st = []
li = []
for i in range(n):
    arr.append(list(map(int, input().split())))

res = int(1e9)
dfs(0)
print(res)

if len(st) > 0 and st[len(st) - 1] > i

이 부분이 아직도 잘 이해가 안간다... 디버깅 돌리면서 손으로 코드 써 봤는데도 저 st[len(st) - 1] > i 조건이 어떤 걸 거르기 위함인지 잘 모르겠다!!!! 아악!

 

 

👻 코드2

# https://www.acmicpc.net/problem/14889
import sys
input = sys.stdin.readline

def dfs(depth, idx):
    global res

    if depth == n // 2:
        s_res, l_res = 0, 0
        for i in range(n):
            for j in range(i+1, n):
                if visited[i] and visited[j]:
                    s_res += arr[i][j] + arr[j][i]
                elif not visited[i] and not visited[j]: # 둘 다 방문을 하지 않았다면 li 팀으로
                    l_res += arr[i][j] + arr[j][i]
        res = min(res, abs(s_res - l_res)) # 최소값 구하기

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

n = int(input())
arr = []
visited = [False] * (n+1)
for i in range(n):
    arr.append(list(map(int, input().split())))

res = int(1e9)
dfs(0, 0)
print(res)

 

---

✔ 후기

코드 이해는 2번이 훨씬 쉬웠다.. 그래서 1번 코드 보고 이해한 것을 바탕으로 2번 코드는 visited 처리를 한다는 힌트를 보고 쉽게 구현할 수 있었다. 하지만 1번 코드가 450ms 2번 코드가 900ms 정도 나와서 거의 2배의 속도가 차이남을 알 수 있다.