도둑질

https://programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

재귀로는 정확도 테스트에서도 시간 초과가 됩니다. 

정확도 점수 부스러기 좀 먹어보겠다는데...
인심 참 야박하네요. 
강호의 정이... 
언제부터 전산계가...

def solution(money):
    max_total = [0]
    for i in range(3):
        find(money[:], i, 0, max_total)
    return max_total[0]


def find(money, pos, total, max_total):
    total += money[pos]
    money[pos - 1] = money[pos] = money[(pos + 1) % len(money)] = 0
    if sum(money) == 0:
        max_total[0] = max(max_total[0], total)
        return
    for i in range(len(money)):
        if money[i] != 0:
            find(money[:], i, total, max_total)

 조금 더 깔끔하게 정리.

def solution(money):
    return max(find(money[:], 0, 0), find(money[:], 1, 0), find(money[:], 2, 0))


def find(money, pos, total):
    max_total = 0
    total += money[pos]
    money[pos - 1] = money[pos] = money[(pos + 1) % len(money)] = 0
    for i in range(len(money)):
        if sum(money) == 0:
            max_total = max(max_total, total)
        elif money[i] != 0:
            max_total = find(money[:], i, total)
    return max_total

동적계획법을 써야겠네요. 

def solution(money):
    answer = 0
    for first in range(2): ##
        dp = [0] * len(money)
        dp[first] = money[first]
        dp[first + 1] = max(dp[first], money[first + 1])
        for i in range(2, len(money) - 1):
            dp[first + i] = max(dp[first + i - 1], money[first + i] + dp[first + i - 2])
        answer = max(answer, *dp)
    return answer


## 0으로 시작, 1로 시작. 총 2회.

효율성  테스트
테스트 1 〉	통과 (777.31ms, 696MB)
테스트 2 〉	통과 (679.84ms, 651MB)
테스트 3 〉	통과 (699.98ms, 678MB)
테스트 4 〉	통과 (771.51ms, 686MB)
테스트 5 〉	통과 (632.80ms, 569MB)
테스트 6 〉	통과 (701.38ms, 657MB)
테스트 7 〉	통과 (400.02ms, 387MB)
테스트 8 〉	통과 (433.91ms, 399MB)
테스트 9 〉	통과 (513.12ms, 467MB)
테스트 10 〉	통과 (692.43ms, 664MB)

슬라이딩 윈도

def solution(money):
    answer = 0
    for first in range(2):
        dp = [0] * 3
        dp[first] = money[first]
        dp[first + 1] = max(dp[first], money[first + 1])
        for i in range(2, len(money) - 1):
            dp[(first + i) % 3] = max(dp[(first + i - 1) % 3], money[first + i] + dp[(first + i - 2) % 3])
        answer = max(answer, *dp)
    return answer

효율성  테스트
테스트 1 〉	통과 (797.22ms, 696MB)
테스트 2 〉	통과 (752.59ms, 651MB)
테스트 3 〉	통과 (798.82ms, 678MB)
테스트 4 〉	통과 (786.50ms, 686MB)
테스트 5 〉	통과 (615.53ms, 569MB)
테스트 6 〉	통과 (756.02ms, 657MB)
테스트 7 〉	통과 (439.54ms, 387MB)
테스트 8 〉	통과 (453.64ms, 399MB)
테스트 9 〉	통과 (499.01ms, 467MB)
테스트 10 〉	통과 (757.13ms, 664MB)

반복 줄여보기..

def solution(money):
    dp1 = [0] * len(money)
    dp1[0] = money[0]
    dp1[1] = max(dp1[0], money[1])

    dp2 = [0] * len(money)
    dp2[0] = money[1]
    dp2[1] = max(dp2[0], money[2])

    for i in range(2, len(money) - 1):
        dp1[i] = max(dp1[i - 1], money[i] + dp1[i - 2])
        dp2[i] = max(dp2[i - 1], money[i + 1] + dp2[i - 2])
    return max(*dp1, *dp2)

효율성  테스트
테스트 1 〉	통과 (656.61ms, 696MB)
테스트 2 〉	통과 (610.07ms, 651MB)
테스트 3 〉	통과 (637.11ms, 678MB)
테스트 4 〉	통과 (603.72ms, 686MB)
테스트 5 〉	통과 (532.63ms, 569MB)
테스트 6 〉	통과 (615.01ms, 657MB)
테스트 7 〉	통과 (341.80ms, 387MB)
테스트 8 〉	통과 (364.22ms, 399MB)
테스트 9 〉	통과 (400.91ms, 467MB)
테스트 10 〉	통과 (588.02ms, 664MB)

슬라이딩 윈도

def solution(money):
    dp1 = [money[0], max(money[0], money[1]), 0]
    dp2 = [money[1], max(money[1], money[2]), 0]
    for i in range(2, len(money) - 1):
        dp1[i % 3] = max(dp1[(i - 1) % 3], money[i] + dp1[(i - 2) % 3])
        dp2[i % 3] = max(dp2[(i - 1) % 3], money[i + 1] + dp2[(i - 2) % 3])
    return max(*dp1, *dp2)

효율성  테스트
테스트 1 〉	통과 (668.60ms, 696MB)
테스트 2 〉	통과 (627.06ms, 651MB)
테스트 3 〉	통과 (639.91ms, 678MB)
테스트 4 〉	통과 (660.33ms, 686MB)
테스트 5 〉	통과 (552.67ms, 569MB)
테스트 6 〉	통과 (593.55ms, 657MB)
테스트 7 〉	통과 (370.84ms, 387MB)
테스트 8 〉	통과 (366.58ms, 399MB)
테스트 9 〉	통과 (422.94ms, 467MB)
테스트 10 〉	통과 (644.72ms, 664MB)