[Programmers] 도둑질

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42897?language=python3 

프로그래머스

 

 

풀이과정

본 문제는 다이나믹 프로그래밍의 유형으로 분류되어 있다. 다이나믹 프로그래밍, DP는 자료구조나 알고리즘 종류라기 보다는 모든 경우를 살펴봐야 할 때 속도 이슈를 해결하지 위한 문제 해결 유형으로 볼 수 있다. 

DP 적용을 위해서는 문제가 다음 두 가지 조건을 만족해야 한다. 
1. DFS/BFS로 풀 수는 있지만 경우의 수가 너무 많은 문제
2. 경우의 수에 중복 연산이 많은 경우

이번 문제도 선택 가능한 모든 경우의 수를 비교해야 풀 수 있는 문제이기에 DP 방식을 적용 해 볼 수 있다. 

연산이 진행됨에따라 연산 결과를 저장하는 공간을 m이라고 할 때 점화식은 다음과 같다

m[i] = max(money[i]+m[i-2], m[i-1]) 

그리고 원형 구조기 때문에 발생 가능한 경우는 아래와 같이 첫 집을 터는 경우 마지막 집을 털지 않고, 첫 집을 털지 않는 경우는 마지막 집까지 탐색한다.

최종 결과는 두 경우 중 큰 값을 선택한다. 

 

Script

def solution(money):
    m_1 = [money[0], money[0]]
    m_2 = [0, money[1]]


    for i in range(2, len(money)-1):
        m_1.append(max(m_1[i-1], money[i]+m_1[i-2]))


    for i in range(2, len(money)):
        m_2.append(max(m_2[i-1], money[i]+m_2[i-2]))

    answer = max(max(m_1), max(m_2))

    return answer