[프로그래머스 동적계획법/DP]도둑질 - Python3 (Lv.4)

문제

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

 

알고리즘

def solution3(money):
    length = len(money)
    # dp배열 2개를 선언한다.
    # dp1 배열은 0번째 집을 터는 경우이다. 따라서, 마지막 집은 털지 않는다
    # dp2 배열은 0번째 집을 털지 않는 경우이다. 따라서, 경우에 따라 마지막 집을 털 수도 있다.
    dp1 = [0] * length
    dp2 = [0] * length

    # dp1 배열은 첫 집을 턴다고 가정했기 때문에, dp[0]의 값을 money[0]으로 초기화한다. 
    dp1[0] = money[0]

    # 0번부터, len(dp1)-2까지 순회한다. 따라서, dp1[-1]은 0이 들어간다. 그러므로 결과값을 정할 때 dp1[-2]를 사용해야 한다
    for i in range(0, len(dp1)-1):
        # dp1[i]를 정함에 있어서, 그 dp[i-2] + money[i]와, dp[i-1]을 비교하는 것과 같다.
        # 이 코드에서는 처음 원소와 마지막 원소가 연결되어 있는 것으로 간주해야하므로, 원형 큐의 형식으로 구현했다.
        # 굳이 그럴 필요는 없는 것 같다. 
        dp1[i] = max(dp1[(i + length - 1) % length],
                     dp1[(i + length - 2) % length] + money[i])
        
    # 첫 집을 털지 않는 경우이기 때문에 , 1부터 반복하고 len(dp2)-1까지 반복한다. 
    for i in range(1, len(dp2)):
        # 위와 비슷하다.
        dp2[i] = max(dp2[(i + length - 1) % length],
                     dp2[(i + length - 2) % length] + money[i])

    print("dp1[-2]: ", dp1)
    print("dp2[-2]: ", dp2)

    # 두 값중 큰 값을 출력한다. 
    answer = max(dp1[-2], dp2[-1])
    return answer

money = [1,2,3,1,5]
print("정답: ", solution3(money))

1. 1. 값을 저장할 dp배열 2개, dp1[], dp2[]를 선언한다.
   • dp1은 첫 집을 터는 경우를 가정하고, 마지막 집은 털지 않는다.
   • dp2는 첫 집을 털지 않는 경우이기 때문에, 마지막 집을 털 수도 안 털 수도 있다. 
2. 2개의 배열을 for문을 통해 dp[i]에 값을 채운다. 각 값은, DP예제 1: 동전 줍기에서 처럼 채운다.
   즉, dp[i] = max(dp[i-2] + money[i] , dp[i-1]) 이렇게 채운다는 뜻이다. 그러나, 첫 원소가 마지막 원소와 이웃한다는 점에서, 원형 큐에서 인덱스를 정하는 것처럼 구현하였다. 
3. dp1[-2]와, dp2[-1] 둘 중 큰 값을 출력한다. dp1은 첫 집을 털기 때문에 마지막 집을 털 수가 없으므로, dp1[-2]를 사용한다. 

 

설명

이 문제 역시 DP예제 1: 동전 줍기와 매우매우 유사하다. 잘 모르겠다면 얼른 가서 공부하고 오도록 해라. 

2020/01/30 - [공부/알고리즘] - [알고리즘 자습]동적계획법(Dynamic Programming) - 동전 선택, 거스름돈 만들기, 동전 줍는 로봇

[알고리즘 자습]동적계획법(Dynamic Programming) - 동전 선택, 거스름돈 만들기, 동전 줍는 로봇

 

예제를 풀었던 것처럼, 아래 점화식에 따라 dp배열에 값을 채우면서, dp배열의 마지막 원소를 return할 것이다.

i = 0 인 경우: DP[i] = money[i]

i > 0 인 경우: DP[I] = max(DP[i-2] + money[i] , DP[I-1]

위의 점화식은, 간단하게 얘기하자면 인접한 원소를 선택할 수가 없기 때문에, 어느 한 원소를 선택할지 말지 결정하기 위해서는 

그 전전의 원소까지의 최적값 + 해당 원소의 값,  그 전 원소가지의 최적값

이 2가지를 비교해야 한다. 

이것이 곧 DP[I] = max(DP[i-2] + money[i] , DP[I-1] 를 의미한다. 

다만 다른 점이 있다면, 첫 원소와 마지막 원소가 이웃한걸로 보기 때문에, 첫 집을 선택하는 경우와 그렇지 않은 경우로 나눠서 문제를 풀었다. 첫번째 경우, 첫 집을 아예 턴다고 가정하고 dp1[0]을 money[0]으로 초기화했고, 두번째 경우는 첫집을 털지 않으므로 dp2는 dp2[0]에 접근해서 값을 채우지 않음으로써 첫번째 집을 배제한다. 

그러고 두 경우 중 큰 값을 정답으로 return한다.

 

결과

올바른 결과를 출력한다. 

후기

공개된 테스트 케이스의 원소의 갯수가 4개이다. 이게 좀 헷갈리는게, 입력 배열의 원소의 갯수가 5개이면 이것저것 고려해야하는데 짝수면 좀 덜하다. 그래서 맞나 싶어서 채점 돌려보면 딴건 다 틀리게 나와서 개짱났다. 근데 이리저리 머리를 굴려 보니, 결국은 DP예제1과 매우 유사하더라. 역시 사람이 기본이 충실해야 한다.