백준 15661번 링크와 스타트

 

15661번: 링크와 스타트

처음에 python3로 코드를 제출하고 시간 초과가 나와다가, pypy로 제출하니 통과가 되었다. 그후로 왜 .. 어떻게 하면 python3로 통과할 수 있으려나 찾아보았다. 결론적으로는 if else문을 줄이고, for 중복문 중간에 if조건을 걸어서 통과할 수 있었다.

처음 코드 : pypy 통과

import sys
input = sys.stdin.readline

n = int(input())
s = []
ch = [0] * n
ans = 100000000
for _ in range(n):
    s.append(list(map(int,input().split())))

def dfs(depth, L, index):
    global ans
    if L == depth:
        star = 0
        link = 0
        for i in range(n):
            for j in range(i + 1, n):
                if ch[i] == 1 and ch[j] == 1:
                    star += s[i][j] + s[j][i]
                elif ch[i] == 0 and ch[j] == 0:
                    link += s[i][j] + s[j][i]
        if depth == 1:
            ans = min(ans, link)
        else:
            ans = min(ans, abs(star - link))
    else:
        for i in range(index, n):
            if ch[i] == 0:
                ch[i] = 1
                dfs(depth , L + 1, i + 1)
                ch[i] = 0

for d in range(1, n//2 + 1):
    dfs(d, 0, 0)
print(ans)

수정한 코드: python3 통과

import sys
input = sys.stdin.readline

n = int(input())
s = []
ch = [0] * n
ans = 100000000
for _ in range(n):
    s.append(list(map(int,input().split())))

def dfs(depth, L, index):
    global ans
    if L == depth:
        star = 0
        link = 0
        for i in range(n):
            if ch[i] == 1:
                for j in range(i + 1, n):
                    if ch[j] == 1:
                        star += s[i][j] + s[j][i]
            else:
                for j in range(i + 1, n):
                    if ch[j] == 0:
                        link += s[i][j] + s[j][i]
        ans = min(ans, abs(star - link))
        if ans == 0:
            return
        return
    for i in range(index, n):
        if ch[i] == 0:
            ch[i] = 1
            dfs(depth , L + 1, i + 1)
            ch[i] = 0

for d in range(n//2,0,-1):
    dfs(d, 0, 0)
    if ans == 0:
        break
print(ans)

큰 차이는,  for 문 중복을 바로 시작하지 않고 중간에 If 문을 넣어줘서, 조금이라도 연산 횟수를 줄이는 것 같다.