프로그래머스(동적계획법)-도둑질-Python

문제 설명

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

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한사항

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

입출력 예

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

 

---

내 문제풀이

1. 집이 원형으로 배치되어 있기 때문에 단순하게 바로 옆 집을 털면 안되는 조건만 고려하면 안되고, 첫 번째 집과 마지막 집을 동시에 털 수 없는 점도 고려해야 한다.

2-1. 먼저 첫 번째 집을 제외하고 마지막 집을 포함하는 경우 첫 번째 집의 돈을 0으로 설정해둔다. 따라서 두 번째 집의 돈도 입력값대로 설정한다. 

2-2. 세 번째 집부터 반복문을 돌며 바로 전 집의 돈 vs 전전 집의 돈+현재 집의 돈을 비교하여 큰 값을 저장한다.

3-1. 마지막 집을 제외하고 첫 번째 집을 포함하는 경우 첫 번째 집의 돈은 입력값대로 설정한다. 그리고 두 번째 집은 첫 번째 집의 돈과 두 번째 집의 돈 중 큰 값으로 설정한다.(첫 번째 집의 돈이 큰 경우 첫 번째 집을 털고 두 번째 집은 털지 않는 것)

3-2. 2-2와 같은 로직으로 len(money)-1만큼만 반복문을 수행하여 마지막 집은 계산하지 않는다.

4. 첫 번째 집을 제외한 경우, 마지막 집을 제외한 경우 중 큰 값을 반환한다.

내 코드 - 파이썬

def solution(money):
    
    # 마지막 집 포함 -> 첫 번째 집 제외
    x1 = [0]*len(money)
    x1[0] = 0
    x1[1] = money[1]
    
    for i in range(2, len(money)):
        x1[i] = max(x1[i-1], x1[i-2]+money[i]) 
        
    # 첫 번째 집 포함 -> 마지막 집 제외
    x6 = [0]*(len(money)-1)
    x6[0] = money[0]
    x6[1] = max(money[0], money[1])
    
    for i in range(2, len(money)-1):
        x6[i] = max(x6[i-1], x6[i-2]+money[i]) 
    
    return max(x1[-1], x6[-1])