내일은 알고리즘

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

파이썬의 내장 메소드를 이용해 List를 자르고, 정렬해서 원하는 값을 출력했습니다.

def solution(array, commands):
    answer = []

    for command in commands:
        start = command[0]
        end = command[1]
        target = command[2]

        arr = array[start-1:end]
        arr.sort()
        answer.append(arr[target-1])

    return answer

print(solution([1, 5, 2, 6, 3, 7, 4], [[2, 5, 3], [4, 4, 1], [1, 7, 3]]))

https://leetcode.com/problems/house-robber-ii/

https://nodingco.tistory.com/101?category=570522 

위 문제의 시리즈로 마찬가지로 DP문제입니다.

집들의 위치가 원형으로 연결되어 첫번째 집과 마지막 집이 붙어있는 형태가 되었다는 조건이 추가되었습니다.

아이디어를 떠올리기가 힘들었는데요. 

간단하게 생각하면 첫번째 집과 마지막 집은 동시에 도둑질을 할 수 없습니다.

집들을 의미하는 입력 리스트를 [첫번째 집~마지막 앞의 집]과 [두번째 집~마지막 집]으로 나누어 각각의 최댓값을 1번 문제와 같은 방식으로 구하면 둘 중에 더 큰 값이 정답이 됩니다.

생각해보면, [첫번째 집~마지막 앞의 집]에서 나오는 정답의 경우는 두가지로 생각해 볼 수 있습니다.

1. 첫번째 집을 도둑질 함 -> 이 경우엔 마지막 집은 당연히 털 수 없었습니다. 하지만 마지막 집을 턴 경우의 값이 더 컸을수도 있겠죠? 그 경우는 [두번째 집~마지막 집]으로 나뉜 범위에서 구한 정답이 됩니다.

2. 첫번째 집을 도둑질 하지 않음 - > 이 경우는 [두번째 집~마지막 집]으로 나눈 것에서 얻어낸 정답과 같습니다. (마지막집의 도둑질여부는 관계없습니다.)

[두번째 집~마지막 집]의 경우도 같은 방식으로 생각됩니다.

따라서 두 범위에서 문제를 풀이하면 둘 중 하나는 무조건 정답이 되게 됩니다.

class Solution:
    def rob(self, nums: list) -> int:
        if(len(nums) == 1):
            return nums[0]
        
        return max(self.sliceRob(nums[1:]), self.sliceRob(nums[:-1]))

    def sliceRob(self, nums: list) -> int:
        dp = [0] * (len(nums) + 1)
        dp[0] = 0
        dp[1] = nums[0]

        for i in range(2, len(nums)+1):
            dp[i] = max(dp[i-1],dp[i-2]+ nums[i-1])

        return dp[-1]


input = [[2,3,2],[1,2,3,1],[1,2,3],[1]]
for i in input:
    print(Solution().rob(i))