[프로그래머스] 동적계획법 4. 도둑질

문제

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

코딩테스트 연습 - 도둑질

---

풀이

어제 풀었던 계단 문제랑 비슷하다고 생각했다.

n번째 계단을 오르는 방법 = n-1번째 계단을 오르는 방법 + n-2번째 계단을 오르는 방법 이었다.

 

이 문제는 풀이는 동일하지만 원형이라서 예외처리를 어떻게 해야할지 고민을 좀 오래 했다.

1,2 둘다 안털고 3을 터는 경우도 있지 않나 싶어서 고민하다가

다른분걸 좀 참고했는데 그냥 단순히 처음 방문한 경우랑 아닌 경우를 나누면 된다고 해서 좀 허무했다,,

구현하고 보니까 visitSecond를 계산하며 1,2 둘다 털지 않고 3만 터는 경우의 수도 계산이 되었다.

def solution(money):
    #누적값
    visitFirst = [money[0], money[0]]
    visitSecond = [0, money[1]]
    
    for i in range(2, len(money)):
        visitFirst.append(max(visitFirst[i-2] + money[i], visitFirst[i-1]))
        visitSecond.append(max(visitSecond[i-2] + money[i], visitSecond[i-1]))
        
    return max(visitFirst[len(money)-2], visitSecond[len(money)-1])

처음집을 방문한 경우, 마지막집을 방문 할 수 없으니 인덱스에서 -1 한 값과 처음집을 방문하지 않은 값의 마지막 누적값을 비교하여 큰 값을 반환한다.

O(n)이다.

 

 

---

다른 사람의 풀이

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)

이분도 첫 집을 털 경우, 첫 집을 털지 않고 두번째 집을 털 경우를 비교했다.