파이썬으로 연속된 세 숫자마다 하나 이상 선택하는 최소합 부분 수열 찾기

문제 정의

숫자로 이루어진 리스트 nums가 주어졌을 때, 다음 조건을 만족하면서 합이 가장 작은 부분 수열(subsequence)을 찾는 것이 목표입니다.

• 연속된 세 개의 숫자로 이루어진 모든 그룹에서 적어도 하나의 숫자를 선택해야 합니다.
• 리스트의 길이가 3보다 작더라도 반드시 하나의 숫자는 선택해야 합니다.

예를 들어 입력이 nums = [2, 3, 4, 5, 6, 7]이라면 출력은 7입니다. 2와 5만 선택하면 조건을 만족하면서 합이 최소가 되기 때문입니다.

접근 방법: 동적 계획법(Dynamic Programming)

이 문제는 동적 계획법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

table[i]를 "nums[i]를 마지막으로 선택하는 유효한 부분 수열의 최소합"이라고 정의합니다. nums[i]를 선택했다면, 그 이전에 선택한 숫자는 반드시 i-1, i-2, i-3 위치 중 하나여야 합니다. 그렇지 않으면 세 개의 연속된 숫자가 모두 선택되지 않는 구간이 생겨 조건을 위반하기 때문입니다. 따라서 점화식은 다음과 같습니다.

table[i] = nums[i] + min(table[i-3], table[i-2], table[i-1])

또한 마지막으로 선택한 숫자는 반드시 마지막 세 위치(n-1, n-2, n-3) 중 하나에 있어야 하므로, 최종 답은 이 세 값 중 최솟값이 됩니다.

알고리즘 단계

1. n을 nums의 길이로 설정합니다.
2. n이 0이면 0을 반환합니다.
3. n이 1이면 nums[0]을 반환합니다.
4. n이 2이면 nums[0]과 nums[1] 중 작은 값을 반환합니다.
5. 크기가 n인 리스트 table을 0으로 초기화하고, table[0], table[1], table[2]에 각각 nums[0], nums[1], nums[2]를 저장합니다.
6. i를 3부터 n-1까지 반복하면서 table[i] = nums[i] + min(table[i-3], table[i-2], table[i-1])을 계산합니다.
7. table[n-1], table[n-2], table[n-3] 중 최솟값을 결과로 반환합니다.

예제 코드

class Solution:
    def solve(self, nums):
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        if n == 2:
            return min(nums[0], nums[1])

        table = [0] * n
        table[0] = nums[0]
        table[1] = nums[1]
        table[2] = nums[2]

        for i in range(3, n):
            table[i] = nums[i] + min(table[i - 3], table[i - 2], table[i - 1])

        res = min(table[n - 1], table[n - 2], table[n - 3])
        return res


ob = Solution()
nums = [2, 3, 4, 5, 6, 7]
print(ob.solve(nums))

입력

[2, 3, 4, 5, 6, 7]

출력

7

복잡도 분석

리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 크기 n의 테이블을 사용하므로 공간 복잡도 역시 O(n)입니다. 최근 세 개의 값만 변수에 유지하도록 구현하면 공간 복잡도를 O(1)까지 줄일 수 있습니다.