[Swift 알고리즘] 백준_24938 (키트 분배하기)

문제

서울과학고 기숙사에는 N개의 방이 일렬로 나열되어 있습니다. 교사들은 교내 방역을 위해 기숙사의 각 방에 진단 키트를 제공했습니다.

그러나 분배 과정에서 실수가 있었고, 방마다 받은 키트의 수가 다르게 되었습니다. 구체적으로, i번 방에서 받은 키트의 수는 A_i개입니다. 학생들은 이 상황을 해결하기 위해 키트를 서로 주고받기로 했습니다.

서로 멀리 떨어진 방끼리 키트를 주고받으면 소란스럽기 때문에, 키트는 인접한 방끼리만 주고받을 수 있습니다. 이때 한 방에서 인접한 다른 방으로 키트 한 개를 건네줄 때 혼잡도가 1 증가합니다. 당연하게도, 키트가 없는 방에서는 다른 방으로 키트를 건네줄 수 없습니다.

혼잡도가 너무 높으면 학생들이 벌점을 받을 수 있기 때문에, 학생들은 혼잡도를 최소로 하여 모든 방이 같은 수의 키트를 가지고 있도록 할 계획입니다. 이때 목표를 달성하기 위한 혼잡도의 최솟값을 구해 봅시다. 전체 키트의 수는 방의 수의 배수임이 보장됩니다.

입력

첫 줄에는 방의 개수를 나타내는 정수 $N$이 주어집니다.

다음 줄에는 각 방이 초기에 받은 키트 수를 나타내는 정수 $A_1, A_2, \cdots, A_N$이 공백을 사이에 두고 주어집니다.

출력

최소의 혼잡도를 출력합니다.

 

 

문제 해결 사고 

1. 키트는 항상 방의 배수 -> 끝에 가면 나누어 떨어집니다.

2. 현재 접근하는 방이 1. 키트를 받아야하는지, 2. 키트가 많은 방으로 부터 키트가 적은 방으로 키트를 옮겨야 하는지, 3. 키트가 많으니 옮겨야 하는지 =>에 대해서 생각했습니다.

3. Index를 1씩 늘려갔을 때 여태 나온 키트를 더한 값과, 현재 Index * kit Everage를 비교하여 키트가 부족하거나 남을 경우 무조건 키트를 옮겨야 하는 상황임.

4. 이것이 현재 index의 카오스 증가량임

 

그림

ind 가 0 일때는 어디선가 +2 만큼의 키트를 받아야 함

 

 

ind 가 1 일 때는 현재 옆으로 2개의 키트를 넘겨준 것을 이미 계산했습니다. 따라서 0부터 1까지의 ind는 상관 안해도 됩니다.

 

마찬가지로 ind가 3일때는 어디선가 키트 한개를 받아야 합니다. 

 

 

표를 완성하면 다음과 같습니다. sub의 절대값의 합이 혼잡도가 됩니다.

 

 

 

전체 코드

import Foundation

func sol() {
    let N = Int(readLine()!)!
    let arr = readLine()!.split(separator: " ").map{Int($0)!}
    let tVal = arr.reduce(0){$0 + $1} / N
    var prevSum = 0
    var res = 0
    for ind in 0..<N {
        let ct = tVal * (ind + 1)
        prevSum += arr[ind]
        let sVal = abs(prevSum - ct)
        res += sVal
    }
    print(res)
}
sol()