Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 모든 작업을 완료하는 데 필요한 최소 시간 구하기

숫자로 이루어진 리스트 nums가 있고, 각 값은 해당 작업을 완료하는 데 걸리는 시간 단위를 나타낸다고 가정해 보겠습니다. 이때 연속되지 않은 작업은 자유롭게 건너뛸 수 있으며, 목표는 모든 작업을 마치는 데 필요한 최소 시간을 구하는 것입니다.

예를 들어 입력이 nums = [11, 6, 8, 16]이라면 결과는 14가 됩니다. 첫 번째와 마지막 작업을 건너뛰면 되기 때문입니다.

접근 방식: 동적 계획법(DP)

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 작업에 대해 '건너뜀'과 '수행'이라는 두 가지 상태를 함께 추적하는 것입니다. 다음 단계를 따릅니다:

  • n := nums의 크기
  • table := n × 2 크기의 행렬을 생성하고 0으로 초기화
  • table[0, 0] := 0 (첫 번째 작업을 건너뛴 경우)
  • table[0, 1] := nums[0] (첫 번째 작업을 수행한 경우)
  • i를 1부터 n-1까지 반복:
    • table[i, 0] := table[i-1, 1] → 현재 작업을 건너뛰려면 이전 작업은 반드시 수행해야 함
    • table[i, 1] := min(table[i-1, 0], table[i-1, 1]) + nums[i] → 현재 작업을 수행하는 경우, 이전 상태 중 더 작은 값 선택
  • 마지막 행 table[n-1]의 최솟값 반환

여기서 table[i][0]은 i번째 작업을 건너뛰었을 때의 누적 최소 시간, table[i][1]은 i번째 작업을 수행했을 때의 누적 최소 시간을 의미합니다. 연속된 두 작업을 동시에 건너뛸 수 없다는 제약 조건 덕분에, 건너뛰는 상태는 항상 직전 작업을 수행한 상태에서만 전이됩니다.

아래 예시 코드를 통해 더 자세히 이해해 보겠습니다.

예제 코드

class Solution:
   def solve(self, nums):
      n = len(nums)
      table = [[0] * 2 for _ in range(n)]

      table[0][0] = 0
      table[0][1] = nums[0]

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

      return min(table[n - 1])

ob = Solution()
nums = [11, 6, 8, 16]
print(ob.solve(nums))

입력

[11, 6, 8, 16]

출력

14