도둑질

• 3집단위로 비교

def solution(a):
    x1, y1, z1 = a[0], max(a[:2]), max(a[0]+a[2], a[1])
    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)

빡고수 코드

3집단위로 비교

x1, y1, z1 은 첫집을 터는 기준 각 집까지 털 수 있는 최대 돈에대한 변수

x2, y2, z2 은 첫집을 안터는 기준 각 집을까지 털 수 있는 최대 돈에대한 변수

역발상의 코드로 보여진다. 보통 풀이는 여태까지 턴 집들의 정보로 다음집을 털지 말지를 정했다면, 이 코드는 마지막집을 털고 이전집들중 어떤것을 털어야 최대인지를 정하는 코드다. 따라서 루프가 끝나면 마지막에 남는 6개의 변수는

x1 : 첫집 포함 마지막 전전집까지 털었을 때의 최대 돈

y1 : 첫집 포함 마지막 전집까지 털었을 때의 최대 돈

z1 : 첫집 포함 마지막집까지 털었을 때의 최대돈

• z1은 첫집 마지막집 둘다 턴 경우가 포함될 수 있으므로 제외

x2 : 첫집 안포함 마지막 전전집까지 털었을 때의 최대 돈

y2 : 첫집 안포함 마지막 전집까지 털었을 때의 최대 돈

z2 : 첫집 안포함 마지막집까지 털었을 때의 최대돈

• x2 < z2 이기 때문에 비교대상에서 제외

따라서

max(x1, y1, y2, z2)

정말 DP문제는 너무 어렵다… 이런사람들 코드 보면 상대적박탈감;