글 읽기 - 파이썬에서 가장 빠른 최솟값 구하는 방법은 무엇인가요?

dodo8 5년 전 0

bitmask와 재귀를 이용한다는 아이디어를 그대로 가져와서 문제를 풀고 있습니다. 다만 문제가 시간초과가 발생하네요. 나름 메모이제이션을 한다고 했는데, 이게 메모이 제이션 문제인지, 다른 문제인지 모르겠어서 하나하나 속도를 빠르게 하는 방법을 찾는 중입니다. 현재 원인으로 생각되는 것은

최솟값 구하는 방법(min())
is None 인지 확인 하는 과정

이렇게 인데 어떻게 해야 더 빠르게 구할 수 없을까요?

# https://www.acmicpc.net/problem/2098
# none 과 int는 같은 리스트 있는 상태에서 min을 쓸 수 없다.
# 시간초과 1번
from sys import stdin

n = int(stdin.readline())
start = 0
visitedAll = (1 << n) - 1

w = [[] for _ in range(n)]
for i in range(n):
    for j in map(int,stdin.readline().split()):
        if j == 0:
            w[i].append(None)
        else :
            w[i].append(j)

dpList = [[ -1 for _ in range(1 << n)] for __ in range(n)]
for j in range(1 << n):
    if j == 1:
        dpList[0][j] = 0
    else :
        dpList[0][j] = None

def DP(now: int, visited: int) -> int:
    global dpList
    if dpList[now][visited] == -1:
        compareList = list()
        visitedBefore = visited & (~(1 << now))
        for i in range(visitedBefore):
            if (visitedBefore >> i) & 1:
                before = i
            else:
                continue
            if DP(before, visitedBefore) is not None and w[before][now] is not None:
                compareList.append(DP(before, visitedBefore)+w[before][now])
        if compareList:
            dpList[now][visited] = min(compareList)
        else:
            dpList[now][visited] = None
        return dpList[now][visited]
    else:
        return dpList[now][visited]

endPointList = list()
for last in range(1,n) :
    if DP(last, visitedAll) is not None and w[last][start] is not None:
        endPointList.append(DP(last, visitedAll)+w[last][start])
print(min(endPointList))

jh05013 5년 전 1

range(visitedBefore)가 문제인 것 같습니다. 저 값의 log 정도만큼만 돌려야 합니다.

dodo8 5년 전 0

visitedBefore.bit_length()로 바꿔주니 해결되었습니다. 해결책 정말로 감사드립니다.

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

문제

문제

출처

ICPC

파이썬에서 가장 빠른 최솟값 구하는 방법은 무엇인가요?

dodo8 5년 전 0

jh05013 5년 전 1

dodo8 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말