글 읽기 - python 시간초과 조언을 구하려 합니다.

hmm0209 3년 전 0

안녕하세요 초보입니다.

14889번 문제를 풀던 도중 시간초과 때문에 질문을 하게 되었습니다.

0 ~ (N-1)까지 재귀를 사용하여 깊이가 N // 2 가 되면 start, link 팀으로 배열을 나누어 해결하려고 했습니다.

check 리스트를 활용하여 팀원의 중복은 해결했으나 시간초과가 발생했습니다.

시간을 줄이는 팁 좀 부탁드려요 ㅠㅠ

또 다른 질문은 check.append(visited)를 하였더니 check에 [[False,False,False.....]] False만 N개 들어있더라고요 ㅠㅠ

check.append(visited.copy())로 해결했는데 혹시 이것도 알려주실 분 계신가요

감사합니다.

def solve(depth, idx):
    global min_diff,out
    if depth == N // 2:
        left = out[:]
        right = []
        for i in range(N):
            if i not in left:
                right.append(i)
        start = 0
        link = 0
        for i in range(len(left)):
            for j in range(len(left)):
                if i != j:
                    start = start + (arr[left[i]][left[j]])
                    link = link + (arr[right[i]][right[j]])
        temp = start - link
        if temp < 0:
            temp *= -1
        if temp < min_diff or min_diff == -1:
            min_diff = temp
        return
    
    for i in range(idx, N):
        out.append(i)
        solve(depth+1, i+1)
        out.pop(-1)

N = int(input())

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

out = []
min_diff = -1
    
solve(0,0)
print(min_diff)


'''
N = int(input())

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

visited = [False for _ in range(N)] 
check = []
out = []
min_diff = -1
def solve(depth):
    global out, visited, min_diff
    if depth == N // 2:
        if visited in check:
            return
        else:
            check.append(visited.copy())
        left = []
        right = []
        for i in range(len(visited)):
            if visited[i]:
                left.append(i)
            else:
                right.append(i)
        start = 0
        link = 0
        for i in range(len(left)):
            for j in range(len(left)):
                if i != j:
                    start = start + (arr[left[i]][left[j]])
                    link = link + (arr[right[i]][right[j]])
        temp = start - link
        if temp < 0:
            temp *= -1
        if temp < min_diff or min_diff == -1:
            min_diff = temp
        return
    
    for i in range(N):
        if not visited[i]:
            visited[i] = True
            out.append(i)
            solve(depth+1)
            visited[i] = False
            out.pop(-1)
    
solve(0)
print(min_diff)
'''

nhjkjh0608 3년 전 1

from copy import deepcopy

deepcopy 가 아마 원하시던게 아닐까 싶습니다
+(느려서 추천드리진않습니다)

20C10 / 2 = 184756

이므로 전부 다 돌려보셔도 되지않을까요

from itertools import combinations 쓰시면 편합니다

imn00133 3년 전 1

copy와 deepcopy에 대해서는

https://blueshw.github.io/2016/01/20/shallow-copy-deep-copy/

를 참고해보시기 바랍니다.

append하는 것이 list일 경우 참조에 의해 값이 계속 같을 수 있습니다.

또한 visted를 확인하기 위해 check에 list를 넣고 비교하는 것은 매우 느립니다.

이 부분을 변경하셔야 될 것 같습니다.

hmm0209 3년 전 0

아~ 해결했습니다!

조언해주신 nhjkjh0608, imn00133님 정말 감사합니다.

제가 해결한 방식은 N과 M(2)를 활용하였습니다.

주석된 것은 시간초과 코드입니다.

N = 6일 때 0~5까지 순서대로 탐색하기 때문에 뒤쪽만 살피면 팀원이 중복되지 않았습니다.

처음은 N과M(1)처럼 푸려다가 시간초과 났었네요;;;

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

python 시간초과 조언을 구하려 합니다.

hmm0209 3년 전 0

nhjkjh0608 3년 전 1

imn00133 3년 전 1

hmm0209 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말