17392(우울한 방학) - 해결

우울한 방학

 

문제

방학동안 기숙사에 홀로 남겨진 인호는 우울하고 고독하다. 다행히 인호는 M일의 방학 동안 N개의 약속이 잡혀있기에, 약속 날짜의 효율적인 배치를 통해 방학 내에 느낄 우울함의 합을 최소화하려고 한다.

인호의 기분은 정수로 표현 가능하며, 기분이 0 미만인 날에 (기분)2 만큼 우울함을 느낀다. 인호의 기분은 오늘 약속이 있다면 약속의 기대행복 값인 Hi이며, 약속이 없으면 어제의 기분에서 1을 뺀 값이다.

인호는 하루에 최대 한 개의 약속을 소화할 수 있으며, N개의 약속들의 순서는 주어진 순서대로여야 한다.

방학은 내일부터 시작이며, 오늘 인호의 기분은 0일 때, 약속을 적절히 배치하여 인호가 방학 동안 느낄 우울함의 합을 최소화하자.

 

입력

첫 번째 줄에는 인호의 약속 개수인 자연수 N과 방학의 일수인 자연수 M이 공백으로 구분되어 주어진다. (0 ≤ N < M < 1000)

두 번째 줄에는 N개의 정수 H1, H2, ..., HN이 공백으로 구분되어 주어진다. Hi는 i 번째 약속의 기대행복 값이다. (1 ≤ Hi < 100)

 

출력

첫 번째 줄에 인호가 방학 동안 느낄 우울함의 합의 최솟값을 출력한다.

---

기본 아이디어로 생각한 것이 우울함이 적기 위해서는 연속으로 기분이 떨어지는 날이 적어야한다는 것.

그리고 우울한 날 자체의 최소값은 구할 수 있다. 이는 약속날의 기분이 기대행복값으로 바로 기분이 좋아지기 때문에 전의 날의 기분에 영향을 받지 않기 때문.

그래서 우울한 날은 전체의 날(M)에서 약속이 있는 날(N), 기대행복 값(Hi) 만큼 빼면 된다. (약속이 있는 날에 기분이 Hi가 되고 -1씩 줄어들면 Hi날 만큼 기분이 0 이상이기 때문)

그리고 이 우울한 날들을 최대한 골고루 분포시키면 되는데 최대한 나눌 수 있는 방법이 N+1개 만큼이다.

약속날 전 후로 우울감을 나누면 최대 약속날 + 1만큼 나눌 수 있기 때문.

나누는 방법은 최대한 골고루 나누어야하기 때문에 전체 우울한 날에서 n+1의 몫만큼 나누고 나머지는 앞에서 차례대로 나누어 주었다.

그렇게 나누고 $n^{2}$의 합 공식($\dfrac{n\left( n+1\right) \left( 2n+1\right) }{6}$)을 사용하여 계산

import sys
input = sys.stdin.readline

N, M = map(int,input().split())

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

# 기분을 커버 할 수 없는 날
sad_days = M - sum(H) - N

# 만약 모두 커버 할 수 있다면 우울함은 0 
if sad_days <= 0:
    print(0)
# 만약 못한다면 이를 우울함이 가장 적게 배치
# 우울함이 적게하기 위해서는 최대한 골고루 가져야함.
else:
    # 최소한 가져야하는 날들
    moc = sad_days//(N+1)
    # 다 나누고 남은 날들
    na = sad_days%(N+1)
    # 계산을 위해 각날들을 저장
    sad_list = [moc] * (N+1)
    # 남은 날들을 고루 분포
    for i in range(na):
        sad_list[i] += 1
    
    # 우울함
    mel = 0

    # 계산 n^2의 합식을 사용
    for i in sad_list:
        mel += (i*(i+1)*(2*i+1))//6

    print(mel)