백준 14899번 스타트와 링크

 

(링크 스타또)

 

차이가 최소가 되는 조합을 찾아야한다. 이문제 역시 완전탐색으로 풀도록 하자

중복되는 순열은 확인할 필요없고, 순서가 다르더라도 구성 요소가 동일하면 중복되는 순열이라는걸 염두에 두고 코드를 작성하자

 

import sys

n=int(sys.stdin.readline().rstrip())
s=[]
team=n//2
for _ in range(n):
    s.append(list(map(int,sys.stdin.readline().rstrip().split())))
stack=[]
v=[0]*n
result=[]

def calc():
    sum1=0
    sum2=0
    for i in range(n):
        for j in range(n):
            if v[i]==v[j]:
                if v[i]==1:
                    sum1+=s[i][j]
                else:
                    sum2+=s[i][j]
    return abs(sum1-sum2)

def dfs():
    if len(stack)==team:
        if len(result)==0:
            result.append(calc())
            return
        result[0]=min(result[0],calc())
        return
    for i in range(n):
        if v[i]==1:
            continue
        v[i]=1
        stack.append(i)
        dfs()
        stack.pop()
        v[i]=0
dfs()
print(result[0])

이렇게 작성했다

이번에도 min적어야 할자리에 max적어놓고 왜 안되냐 이러고 있었다. 제발 문제를 잘 확인하자

 

음

좀더 최적화 해보자

 

아니 분명히 코드 작성하기 전에

이렇게 생각해놓고 왜 실제로 작성할때는 무지성으로 작성한거냐

 

다시 작성하자

import sys

n=int(sys.stdin.readline().rstrip())
s=[]
team=n//2
for _ in range(n):
    s.append(list(map(int,sys.stdin.readline().rstrip().split())))
stack=[]
v=[0]*n
result=[]
stack_index=[]

def calc():
    sum1=0
    sum2=0
    for i in range(n):
        for j in range(n):
            if v[i]==v[j]:
                if v[i]==1:
                    sum1+=s[i][j]
                else:
                    sum2+=s[i][j]
    return abs(sum1-sum2)

def dfs():
    if len(stack)==team:
        if len(result)==0:
            result.append(calc())
            return
        result[0]=min(result[0],calc())
        return
    for i in range(n):
        if v[i]==1 or (len(stack)!=0 and stack_index[-1]>i):
            continue
        v[i]=1
        stack.append(i)
        stack_index.append(i)
        dfs()
        stack.pop()
        stack_index.pop()
        v[i]=0
dfs()
print(result[0])

수정했다

 

다시가보자

 

너무 느려...

채점도 너무 오래걸린다