강의로 돌아가기
임정섭

테스트 4에서 실패가 나고 효율성 테스트를 1번을 제외하고는 통과를 못합니다

코드를 어떻게 고쳐야 테스트 4를 성공하고, 효율성 테스트를 성공할 수 있을까요?

작성중인 코드―solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import sys
sys.setrecursionlimit(10**6)

def solution(left, right):
    cache={}
    def backtrack(l,r,cur_score):

        if tuple(l+r) in cache:
            return cache[tuple(l+r)]

        if l==[] or r==[]:
            return cur_score
        else:
            if r[0]<l[0]:
                cur_score=backtrack(l,r[1:],cur_score+r[0])

            else:
                left_thrown=backtrack(l[1:],r,cur_score)
                both_thrown=backtrack(l[1:],r[1:],cur_score)

                cache[tuple(l[1:]+r)]=left_thrown
                cache[tuple(l[1:]+r[1:])]=both_thrown

                cur_score=max(left_thrown,both_thrown)
            return cur_score                               

    return backtrack(left,right,0)
  • JUNG-SUNGMIN
    backtracking을 의도한 문제가 아니라 dynamic 기법으로 해결하셔야할것같습니다. JUNG-SUNGMIN 2018.10.31 19:01
0 개의 답변
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.