[프로그래머스] 도둑질 / Python

문제주소 :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

 

<풀이법>

▒ 한줄 개념: 0~n-2 한번, n-1~1 한번 ▒ 

이 문제에서 나타나는 조건은 2가지가 있습니다.

1. 이웃한 집을 선택할 수 없다.

2. 집들이 원형의 형태를 하고 있다. (첫 번째 집, 마지막 집이 이웃한다.)

이 두 가지 조건을 해결해야하는 문제입니다.

 

1. 이웃한 집을 선택할 수 없다.

동적 계획법 문제에서 자주 등장하는 조건입니다. 이웃한 집을 선택할 수 없으므로, -2 위치 또는 -3 위치의 집의 최대값을 가져와야합니다. 따라서 점화식이 다음과 같이 나타납니다.

dp[i] = max(dp[i-2], dp[i-3]) + money[i]

또한 결과를 반환하는데 있어, 단순히 dp[n-1]을 반환하는 것이 아니라, max(dp[n-1], dp[n-2])를 해주어야 합니다.

그 이유는, 총 10개의 집이 있다고 할 때, 나올 수 있는 최댓값이 다음과 같기 때문입니다.

dp[10] = max(dp[8], dp[7]) + money[10]

dp[9] = max(dp[7], dp[6]) + money[9]

dp[9]와 dp[10]은 서로 비교되지 못하고 반복문이 종료되므로, n-1, n-2 모두가 최댓값 후보가 됩니다.

 

2. 집들이 원형의 형태를 하고 있다. (첫 번째 집, 마지막 집이 이웃한다.)

이게 처음보는 형태의 조건이었습니다. 따라서 고민을 좀 많이 해보았는데, 생각보다 쉽게 해결할 수 있었습니다.

이는 바로, 0번 집을 선택하지 못하는 경우의 dp와, n-1번 집을 선택하지 못하는 경우의 dp를 각각 나누어서 구하고, 그 결과를 비교해서 최댓값을 얻어내는 것입니다.

쉽게 말해, max(첫 번째 집이 없다고 가정하고 dp, 마지막 집이 없다고 가정하고 dp) 가 최댓값이 되는 것입니다.

첫 번째 집과 마지막 집은 무조건 이웃한 집이기 때문에, 무슨 일이 있어도 둘이 한꺼번에 선택 될 수 없습니다. 

그러므로 애초에 두 집이 없는 환경을 각각 한번씩 만들어주어서 dp를 계산하고, 최종적으로 나온 2가지의 최댓값을 뽑아낸다면 정답이 됩니다.

 

 

<코드(Python)>

def solution(money):
    money2 = money[:-1]
    money = money[1:]
        
    dp = money[:2] + [money[0]+money[2]] + [0 for i in range(len(money)-3)]
    dp2 = money2[:2] + [money2[0]+money2[2]] + [0 for i in range(len(money2)-3)]
    
    for i in range(3, len(money)):
        dp[i] = max(dp[i-2], dp[i-3]) + money[i]
        dp2[i] = max(dp2[i-2], dp2[i-3]) + money2[i]

    return max(dp[-2:]+ dp2[-2:])

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest