[python] 프로그래머스 - 도둑질

🤔문제 해결

Lv4 | DP

 

"인접한 집은 털 수 없다" 까지는 크게 어려운 문제가 아니지만

"마을이 원형으로 되어 있다" 에서 한번 더 생각하게 하는 문제!!

-> 0번째 집을 터는 경우( 마지막 집을 털지 못한다 )와 0번째 집을 안터는 경우 두가지로 나눌 수 있다.

 

먼저 0번집을 털 경우!

• 0번집에 들렀을 때 가장 많은 돈을 가져오는 경우는 0번집을 턴다. dp[0] = money[0]
• 1번집에 들렀을 때 가장 많은 돈을 가져오는 경우는 1번집을 터는 경우지만 우리는 1번집을 반드시 털었다고 가정했으므로 인접한 2번집은 털 수 없다. dp[1] = 0
• 2번집에 들렀을 때: 인접한 1번집이 아닌 0번집 또는 -1번집(2번일 때는 없다) 중 돈을 많이 가져왔던 집에서 온다.
  dp[2] = money[i] + max(dp[i-2], dp[i-1])
• 마지막으로 n번째 집은 없다고 가정해야한다. (1번집을 털었으므로 1번과 인접한 n번집은 털면 안됨!!)

다음 0번집을 안터는 경우!

• 0번집을 털지 않으므로 dp[0] = 0
• 0번집 안털었으니 1번집은 탄다. dp[1] = money[1]

💨

💻소스 코드

def solution(money):
    answer = 0
    n = len(money)
    # 0번집 털기
    dp1 = [0] * (n - 1)
    dp1[0] = money[0]
    dp1[1] = 0
    for i in range(2, n - 1):
        dp1[i] = money[i] + max(dp1[i - 2], dp1[i - 3])

    # 0번집 안털기
    dp2 = [0] * (n)
    dp2[0] = 0
    dp2[1] = money[1]
    for i in range(2, n):
        dp2[i] = money[i] + max(dp2[i - 2], dp2[i - 3])

    answer = max(max(dp1), max(dp2))
    return answer

 

 

📕문제 확인

출처: 프로그래머스

링크: https://programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

---

문제 설명

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

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

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

제한사항

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

입출력 예

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