백준 14889번 파이썬 - 스타트와 링크

 

 

14889번: 스타트와 링크

아이디어는 금방 떠올랐지만.! 시간초과가 나와버렸다. 왜 시간초과가 나왔나 생각해 보았다.

재귀로 조합을 구현했을 때 시간 복잡도: O(2^n)

이 문제에서는 20이 최대 n이고, 2^20 => 100만번 연산 + 재귀가 끝날때 for중복 2번 ( 최대 200번 ) => 2억연산 초과... (1억회당 1초)

내가 for중복과 사실살 필요없는 배열을 사용, 2차원 배열 index가  0부터 시작하는 것을 1로 마추려다,, 등등의 이유로 시간 초과가 났다.

정말 당연한 거지만, 아이디어가 떠올라도 구체적으로 적용하기 전에 빠르게 시간 복잡도를 생각해보고 시작하자.

포인트 및 풀이

방문 여부를 체크하는 배열(ch)을 통해서 재귀 함수 호출을 통해 (depth가 n//2, 즉 재귀 호출 종료조건) n//2 만큼의 팀을 구성했다면,

방문한 숫자 일때는 star팀의 능력치를 계산하고 동시에 방문하지 않은 숫자일 때는 link팀의 능력치를 한 번에 계산해서 두 팀의 능력치 차를 구한다.

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = []
ch = [False] * n # 방문여부 체크하는 배열
ans = 100000000

def dfs(L, index):
    global ans
    if L == n // 2:
        star = 0
        link = 0
        for i in range(n):
            for j in range(i + 1, n):
                if ch[i] and ch[j]:# 방문한 숫자 이외에는 전부 다른 팀 이므로 한번에 같이 계산
                    star += arr[i][j] + arr[j][i]
                elif not ch[i] and not ch[j]:
                    link += arr[i][j] + arr[j][i]
        ans = min(ans, abs(star - link))
    else:
        for i in range(index, n):
        # ch[0]을 조건에 붙인 이유: 처음 뽑았던 숫자를 포함했을 때의 경우로만 모든 조합 팀을 구성해도 모든 팀 구성이 나온다
        #(어차피 능력치의 차이를 구하는 것이기 때문.
        # star:[1,2,3] link:[4,5,6] 팀 구성이면, 이와 반대의 경우도 같다고 간주.)
            if L == 0 or (not ch[i] and ch[0]):
                ch[i] = True
                dfs(L + 1, i + 1)
                ch[i] = False

for _ in range(n):
    arr.append(list(map(int,input().split())))

dfs(0,0)
print(ans)
# 느낀점. 
# 시간복잡도를 미리 생각하자. 
# 이전 풀이법 시간초과 난 이유: 조합은 O(2^n) => 20이면 100만, for중복 두번 -> 200번 + 조건문 다수 =>초과.
# 2차원 배열에서 숫자 맞추려고 index가 0 인 부분에 0을 insert 하지말자.
#  -> index out of range 오류 발생 막기 위함.
# 최소한의 반복문과 조건, 배열을 사용하자.