Python WEIRD 최적화 질문

  • ckdalsdhdp
    ckdalsdhdp

    안녕하세요 파이썬으로 Weird Number 문제를 풀고 있습니다.
    동적계획법으로 이 문제를 해결했고 max를 지정하는 등의 최적화까지 했는데도 시간초과가 나네요 혹시 제가 놓친 최적화 부분이 있으면 가르쳐주시면 감사하겠습니다. Weird Number을 판별하는 부분 소스를 첨부하겠습니다.

    WEIRD

    def can_make(divisors, original_num):
    bool_divisors = [False for _ in xrange(original_num + sum(divisors) + 1)]
    bool_divisors[0] = True
    max = 0

    for i in xrange(len(divisors)):
        for j in xrange(max, -1, -1):
            if bool_divisors[j]:
                if max < j+divisors[i]:
                    max = j+divisors[i]

                bool_divisors[j+divisors[i]] = True
                if j+divisors[i] == original_num:
                    return True

    if bool_divisors[original_num]:
        return True

    return False


    9년 전
1개의 댓글이 있습니다.
  • ckdalsdhdp
    ckdalsdhdp

    j+divisors[i] 이 부분을 변수 하나로 둬서 시간을 꽤 많이 단축시켰습니다. 그래도 여전히 시간초과가 나네요 문제에서는 ㅜㅜ


    9년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.