[프로그래머스] '도둑질' 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]
   
   [Most 1 의 풀이]

---

 

문제 설명

 

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

 

 

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

 

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

 

 

 

 

제한사항

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

 

입출력 예

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

알고리즘 분석

 

• 나의 풀이

def solution(money):
    N = len(money)  # money의 크기 
    dy1, dy2 = money[:], money[:]  # 마지막 집을 무조건 터는 경우, 첫 집을 무조건 터는 경우

    dy1[0] = 0
    dy2[1] = max(money[0], money[1])

    for i in range(2, N):
        dy1[i] = max(dy1[i-2]+dy1[i], dy1[i-1])
        if N-1 > i:
            dy2[i] = max(dy2[i-2] + dy2[i], dy2[i-1])
        
    return max(dy1[-1], dy1[-2], dy2[-1], dy2[-2])

 

 

 

코딩테스트 연습 - 도둑질