[백준 17392번] 우울한 방학

17392번: 우울한 방학

n, m = map(int,input().split())

h = list(map(int,input().split()))

def getUnhappy(num):
    total = 0
    
    for i in range(1,num+1):
        total += i**2
    
    return total

happy = sum(h) + len(h)
unhappy = m - happy

area = [0] * (n+1)

index = 0

for i in range(unhappy):
    area[index] += 1
    index += 1

    if index >= n+1:
        index = 0

print(sum([getUnhappy(x) for x in area]))

이번 문제는 약속이 있는 날은 행복지수 Hi + 1일 만큼 기분이 유지되고 약속이 없는 날에는 기분이 -1 씩 떨어지는데, 기분이 0 미만인 날에는 (기분)^2 만큼 우울감을 느낀다는 가정하에 최소한으로 느낄 수 있는 우울감을 구하는 문제이다.

 

처음에 어떻게 풀지 고민한 끝에 행복지수 Hi + 1일 만큼은 기분이 0 이상으로 유지될 것이고, 기분이 0 미만인 날이 연속적으로 이어지는 것 보다 골고루 분배해서 최대한 연속되는 날이 적게 만들어주는 것이 더 우울감을 최소화할 수 있다는 것을 알게되었다.

 

따라서 약속의 개수가 n개라면 n + 1개의 분배 장소가 정해진다. n+1개의 구간에 최대한 균등하게 분배해야 하기 때문에 n+1개의 구간에 1씩 각각 한개씩 순회하면서 우울한 날을 넣어주면 된다.

 

그 후 연속된 날짜를 인자로 받고, 총 얻게 되는 우울감을 리턴하는 getUnhappy() 함수를 사용하여 그 합을 구해주었다.

 

Greedy를 오랜만에 풀어볼 수 있었던 좋은 문제였다 :)