APCS Nov 2021 - g597 Q3 [Python]

문제 설명:

n대의 기계가 한 줄로 놓여 있습니다. i번째 기계는 데이터 한 단위를 만드는 데 t[i]만큼의 시간이 걸립니다. m개의 작업이 있으며, i번째 작업은 [l[i], r[i]] 위치의 각 기계가 w[i]단위의 데이터를 생산해야 합니다. n대의 기계 순서를 바꿔 모든 작업에 걸리는 총시간을 최소화하세요.

[name=BlackInk7777] 반복문으로 구간의 값을 하나씩 더하면 시간 초과가 나므로 차분 배열을 사용해 속도를 높입니다.

---

차분 배열 설명

크기가 5이고 모든 값이 0인 dur 배열을 가정합니다: Array = [0,0,0,0,0]. [2,5]의 모든 원소에 1을, [3,5]의 모든 원소에 2를 더하려고 합니다.

차분 배열 적용

1. diff 초기화: diff = [0, 0, 0, 0, 0, 0, 0]. 원래 배열의 끝 뒤에도 여유 공간을 둡니다.
2. 첫 구간 [2,4]에 더하기: 위치 2에 1을 더해 diff = [0, 0, 1, 0, 0, 0, 0]으로 만듭니다. 위치 4 바로 다음인 위치 5에서 1을 빼면 diff = [0, 0, 1, 0, 0, -1, 0]입니다.
3. 둘째 구간 [3,5]에 더하기: 위치 3에 2를 더해 diff = [0, 0, 1, 2, 0, -1, 0]으로 만듭니다. 위치 5 바로 다음인 위치 6에서 2를 빼면 diff = [0, 0, 1, 2, 0, -1, -2]입니다.
4. 누적 합으로 dur 복원:
   • i = 1: dur[1] = 0.
   • i = 2: dur[2] = 1(누적 합 1).
   • i = 3: dur[3] = 3(1 + 2).
   • i = 4: dur[4] = 3(3 + 0).
   • i = 5: dur[5] = 2(3 - 1).
   • i = 6: dur[6] = 0(2 - 2).

결과

최종 배열은 dur = [0, 0, 1, 3, 3, 2]입니다.

---

구현

def main():
    n,m = map(int,input().split())
    dur = [0] * (n + 2)
    diff = [0] * (n + 2)

    for _ in range(m):
        l,r,w = map(int, input().split())
        diff[l] += w
        diff[r+1] -= w

    machine = [int(num) for num in input().split()]

    currect = 0

    for i in range(1 ,len(diff)):
        dur[i] = currect + diff[i]
        currect = dur[i]

    dur.pop(0)
    dur.pop()

    times = 0

    machine.sort(reverse=True)
    dur.sort()

    for i in range(len(dur)):
        times += dur[i] * machine[i]

    print(times)
    
if __name__ == "__main__":
    main()

핵심 개념

• 차분 배열

• pop 사용법: [(배열)].pop(위치)

  예:

  the_list = [0,1,2,3,4]
  the_list.pop(0) // output: [1,2,3,4]
  

이 글은 번체 중국어 원문을 AI로 번역했습니다. 의미나 표현에 차이가 있을 수 있으니 정확한 내용은 번체 중국어 원문을 기준으로 확인해 주세요.