[프로그래머스] LV.4 도둑질 / 파이썬(Python)

 

📜 문제 설명

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

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

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

 

제한사항

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

 

🔗 문제 링크

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

프로그래머스

 

💡 문제 풀이

DP 문제

이전에 풀었던 스티커 문제와 완벽하게 동일한 문제다. 

https://honeynyancat.tistory.com/61

풀이도 동일하게 진행했다. 레벨 4치고는 비교적 수월했던 문제이다.

[프로그래머스] LV.3 스티커 모으기(2) / 파이썬(Python)

 

변수로 주어지는 리스트에서 값들을 가져와서 그 합계가 최대한 큰 값을 만든다.

이 때 제한사항은 연속으로 두 값을 가져올 수 없으며 리스트의 시작과 끝도 연결되어 있는 것으로 간주한다.

그래서 크게 보면 두 가지의 경우의 수가 있다. 1) 리스트의 첫 번째 값을 가져간다. 2) 리스트의 마지막 값을 가져간다.

첫 번째 요소와 마지막 요소를 동시에 가져갈 수 는 없기 때문에 두 경우 각각의 최대 수를 구하고 마지막에 두 경우 중 합계가 더 큰 경우가 정답이 된다.

 

def solution(money):
    answer = 0
    # 도둑질을 해서 얻을 수 있는 이득의 경우의 수
    check = [[0, 0] for _ in range(len(money))]
    
    # 0번에 첫 번째 값을 포함할 경우, 1번에 마지막 값을 포함할 경우를 담아본다
    check[0][0] = money[0]
    check[1][0] = money[0]
    check[1][1] = money[1]
    
    for i in range(2, len(money)):
        check[i][0] = max(check[i-1][0], check[i-2][0] + money[i])
        check[i][1] = max(check[i-1][1], check[i-2][1] + money[i])
    
    return max(check[-2][0], check[-1][1])