[프로그래머스] (LV4) 도둑질

도둑질

Python3

문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

입출력 예

money	return
[1, 2, 3, 1]	4

풀이

---

python

def solution(money):

    f = [0] * len(money)
    f[0] = f[1] = money[0]
    
    for i in range(2, len(money)-1):
        f[i] = max(f[i-2] + money[i], f[i-1])
    
    s = [0] * len(money)
    s[1] = money[1]
    
    for i in range(2, len(money)):
        s[i] = max(s[i-2] + money[i], s[i-1])        
    
    return max(f+s)

설명

---

동적계획법(Dynamic Programming) 유형의 꽤나 깊은 생각을 요하는 문제다.

반복문을 돌며 현재 집을 기준으로 지난 집들의 최댓값을 누적시키는 것이 포인트다.

여기까지는 기본적인 DP의 유형을 따르지만, 첫 번째 집이 선택되는 경우와 그렇지 못한 경우에 따라 마지막 집을 선택할 수 있는지에대한 여부가 갈리기 때문에 이를 신경 쓰는 과정에서 다소 시간이 걸렸다.

또한, 직전 집의 최댓값을 바로 다음 인덱스의 집에서도 적용할 수 있다는 생각은 처음에 떠오르지 않았다.

몇 번의 시행착오를 거듭한 끝에 답을 구할 수 있었고, 아이러니하게도 풀이를 계속 고민할 수록 코드의 길이는 짧아졌다.

DP는 풀이에 도달하기 까지 깊은 생각을 요하지만, 막상 풀이는 매우 짧고 간결한 것 같다.

무언가 DP 유형의 문제를 풀면서 풀이가 지저분하게 길어지고 있다면, 현재 문제를 잘못 접근하고 있다는 생각을 할 필요가 있다.