[프로그래머스] 도둑질, Python3

문제는 여기!

 

안녕하세요! 이번 시간에는 프로그래머스 고득점 kit DP파트, 난이도 Level4 문제였던 도둑질 문제를 풀이해보겠습니다.

제한사항 및 주의사항

각 집은 동그랗게 배치되어 있습니다.

인접한 두 집을 털게 되면 경보가 울립니다. 우리는 경보가 울리지 않게 집을 털어야 하고, 최대한 돈을 많이 털어야 합니다.

마을에 있는 집은 3 이상 1,000,000 이하 입니다.

money 배열의 각 원소는 0 이상 1,000 이하 정수입니다.

풀이전략

각 집은 동그랗게 배치되어 있기 떄문에, 첫 번째 집을 털게 될 경우 마지막 집은 털 수 없습니다. 그래서 저는 첫 번째 집을 털 경우 dp[0][i]와 첫 번째 집을 털지 않을 경우 dp[1][i]로 나누어서 풀었습니다.

그럼 이제, dp[i]번째는 어떤 의미를 갖고 있는지 살펴보겠습니다. 그 전에 우리는 dp 리스트를 2차원으로 정의해야 합니다. row(첫 번째 집을 털 경우와 털지 않을 경우)를 2, column(집의 갯수)을 len(money) 만큼 초기화하고 나서, dp[0][0] 과 dp[0][1]은 money[0]이 됩니다. 첫 번쨰 집을 털 경우 두 번째 집은 털 수 없기 때문입니다.

dp[1][0]은 첫 번째 집을 털지 않을 경우이기 때문에 0으로, dp[1][1]은 첫 번째 집을 털지 않았기에 당연히 두 번째 집을 털어야 하니까 money[1]이 됩니다. 자, 이제 점화식을 도출해보겠습니다.

dp[0][i] : 첫 번째 집을 털고, i 번째 집을 털 경우의 최대 돈 액수

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

dp[1][i] : 첫 번째 집을 털지 않고, i 번째 집을 털 경우의 최대 돈 액수

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

단, 첫 번째 집을 털 경우에 i가 마지막이라면 마지막집은 털지 않고 (max로 비교하지 않고) 그대로 dp[0][i - 1]을 주어야 합니다. 감이 잡히시죠?

그 다음, 첫 집을 털지 않았을 때의 끝 column index, 첫 집을 털었을 때의 끝 column index 두 값을 비교해 최댓값을 리턴하면 정답 판정을 받을 수 있는 문제였습니다.

코드

def solution(money):
    n = len(money)
    dp = [[0 for _ in range(n)] for _ in range(2)]
    dp[0][0], dp[0][1] = money[0], money[0]    # 첫 번째 집을 털은 경우
    dp[1][1] = money[1]                        # 첫 번째 집을 털지 않은 경우
    for i in range(2, n):
        if i == n - 1:
            dp[0][i] = dp[0][i-1]
            dp[1][i] = max(dp[1][i-2] + money[i], dp[1][i-1])
        else:
            dp[0][i] = max(dp[0][i-2] + money[i], dp[0][i-1])
            dp[1][i] = max(dp[1][i-2] + money[i], dp[1][i-1])

    return max(dp[0][n-1], dp[1][n-1])

오늘의 풀이는 여기까지 입니다! 피드백은 언제나 환영해요!