[ Lv 4 ] [ DP ] 도둑질

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

코딩테스트 연습 - 도둑질

---

풀이 과정

---

• 썩 좋은 문제인거같지는 않음.. DP 테이블을 구성하면 시간초과가 나와서 찾아보니 변수로 풀이하면 시간초과가 나지 않는다고 하여 변수로 DP 풀이 함.

1. 동그랗게 배치되어 있으므로 1번에 집이 배치되던가 배치되지 않던가 두가지 경우로 나누어서 풀이해야 함.

   • 1번에 집이 배치되었다면 2번에는 반드시 배치가 되지 않은 상태로 3번부터 진행
   • 1번에 집이 배치되어있지 않다면 2번에는 배치가 될수도, 안될수도 있으니 각각에 맞춰 채운 후 진행

2. 최대 금액을 출력한다.

   • 1번에 집이 배치가 된 상태이면서 마지막 번호에 배치가 되지 않은 경우
   • 1번에 집이 배치가 되지 않은 상태이면서 마지막 번호에 배치가 되었거나 / 되지 않은 경우
   • 총 세가지 경우중 최댓값을 출력해주면 된다.

3. 아래 소스 참고

   • a -> 1번 뽑음 & 현재 번호의 집은 털지 않음
   • b -> 1번 뽑음 & 현재 번호의 집 털음
   • e -> 1번 뽑지 않음 & 현재 번호의 집 털지 않음
   • f -> 1번 뽑지 않음 & 현재 번호의 집 털음

---

소스 코드

---

def solution(money):

    # 1번을 뽑았을 때
    a, b, c, d = 0, 0, 0, 0
    a, b = money[0], money[0]

    # 1번을 뽑지 않았을 때
    e, f, g, h = 0, 0, 0, 0
    e, f = 0, money[1]

    for i in range(2, len(money)):
        c = max(a, b)
        d = max(a + money[i], b)
        g = max(e, f)
        h = max(e + money[i], f)

        a, b = c, d
        e, f = g, h


    answer = max(a, e, f)
    return answer