도둑질(DP이용)

스위치를 이용하여 경우의수 나눔

def solution(money): # 1,000,000개 이하 0(n)에서 끝내야한다
    if len(money) ==3: return max(money) #예외처리
    cur = money[:2] #[a,b]
    cur.append(cur[0] + money[2]) #[a,b,c] -> [0,b,c]
    switch = (max(cur[0],cur[1]) == cur[0]) #첫번째가 뽑혓냐
    
    
    #cur[3] = max(cur[0],cur[1]) +money[3] #[0,b,c,d] -> b,c크기비교 x
    #cur[4] = max(cur[1],cur[2])  +money[4] # [0,0,c,d,e] 
    #cur[5] = max(cur[2],cur[3]) + money[5] # [0,0,0,d,e,f] -> d,e 크기비교 x
    #cur[6] = max(cur[3],cur[4]) +money[6] #[0,0,0,0,0,e,f,g]
    for idx in range (3,len(money)):
        if idx == (len(money)-1) and switch == True:
            if money[0]< money[-1]: #마지막 놈 넣을지 말지
                cur.append(max(cur[idx-3],cur[idx-2])+money[idx]-money[0])
            break
        cur.append(max(cur[idx-3],cur[idx-2])+money[idx])
    return max(cur[-1],cur[-2])

점수 75점

→ 함정 : 원형테이블 문제로 첫번째와 마지막을 고려해야한다

이유 : 다음과 같이 전의 과정이 나중에도 미치는 경우 나중에 제거하기엔 늦다

(먼저 제거할 수 있는 방안을 고안해야 한다)

두가지 경우로 나눔

def solution(money): # 1,000,000개 이하 0(n)에서 끝내야한다
    if len(money) ==3: return max(money) #예외처리
    answer = []
    money1 = money[:]
    money1[0] = 0
    money2 = money[:-1]
    lst = [money1,money2]
    for money in lst:
        cur = money[:2] #[a,b]
        cur.append(cur[0] + money[2]) #[a,b,c] -> [0,b,c]
        for idx in range (3,len(money)):
            cur.append(max(cur[idx-3],cur[idx-2])+money[idx])
        answer.append(max(cur[-1],cur[-2]))
    return max(answer)
#cur[3] = max(cur[0],cur[1]) +money[3] #[0,b,c,d] -> b,c크기비교 x
#cur[4] = max(cur[1],cur[2])  +money[4] # [0,0,c,d,e] 
#cur[5] = max(cur[2],cur[3]) + money[5] # [0,0,0,d,e,f] -> d,e 크기비교 x
#cur[6] = max(cur[3],cur[4]) +money[6] #[0,0,0,0,0,e,f,g]

베스트 풀이 파이썬적인 문법

def solution(a):
    x1, y1, z1 = a[0], a[1], a[0]+a[2] #처음을 넣는 경우
    x2, y2, z2 = 0, a[1], a[2] #처음을 넣지 않는 경우
    for i in a[3:]:
        x1, y1, z1 = y1, z1, max(x1, y1)+i
        x2, y2, z2 = y2, z2, max(x2, y2)+i
    return max(x1, y1, y2, z2)