[프로그래머스]도둑질[Python]

문제링크

프로그래머스-코딩테스트연습-DP-도둑질

풀이 전 계획 및 생각

n 이 3보다 크니까
k번째 집까지 털었을 때 얻는 수익의 최댓값 =
max(k-2번째집까지 턴 수익+k번째 집에 있는 돈,k-1번째 집까지 턴 수익)
의 점화식을 생각해냈다.

인접한 두 집은 털 수 없는데, 집들이 동그랗게 배치되어있으므로, 1번째 집과 n번째 집은 이웃한 집이 된다. 그래서 경우를 첫번째 집을 털지말지 고민하는 경우의 수와 아예 털지않기로 생각하는 경우의 수로 나눠서 접근했다.

그래서 1번째 집을 터는 경우에는 마지막 집은 고려대상에서 제외시켰고
이 경우 초기화를 array_1 = [money[0],max(money[0],money[1])]로 초기화 했다. 이때 array_1[1]이 max(money[0],money[1])인 이유는 1번째 집을

반대로 마지막 집을 터는 경우에는 첫번째 집
1번집 안터는 경우 -> n번째집 털 수 있다.
이 경우 초기화를 [0,money[1]]

풀이

def solution(money):
    array_1 = [money[0],max(money[0],money[1])]+[0]*(len(money)-2)
    array_2 = [0,money[1]]+[0]*(len(money)-2)
    for i in range(2,len(money)-1):
        array_1[i] = max(array_1[i-1],array_1[i-2]+money[i])
    for i in range(2,len(money)):
        array_2[i] = max(array_2[i-1],array_2[i-2]+money[i])
    return max(max(array_1),max(array_2))

풀이하면서 막혔던 점과 고민했던 점

처음에 점화식을 세울 때, 1번째 집과 n번째 집이 이웃집이라는 것을 잊은 상태로 문제를 풀었다가 빙빙 돌아갔다. 문제를 구조화하지않고 달려들었던게 문제였던 것 같다.

풀이 후 알게된 개념과 소감

문제를 풀 때는 먼저 구조화를 한 다음, 어떻게 작성할 것인지에대한 전략을 가지고 들어가는 것이 꼭 필요하다는 것을 다시 느꼈다. 아무리 급해도 해야하는 것이라는 생각이든다.