[백준-파이썬] 17392. 우울한 방학

문제 보러 가기~

ㅠㅠㅠ 그리디 문제는 아이디어 떠올리기가 어려워서 다른 분들 것을 참고할 때가 많았다..
그러다가 오랜만에 스스로 푼 문제..!!

접근

일단 문제에서 구할 것은 '우울함의 합'을 최소화하자는 것이다.
우울함은 기분 0 미만인 날에서 (기분)^2이다.
약속의 순서는 바꿀 수가 없이 언제 할지 배치하는 것이다.

일단 기분이 0 이상이면 괜찮은 상황이다.
=> 모든 날의 기분이 0 이상일 수 있으면 정답은 0이다.
=> 모든 날의 기분이 0 이상일 수 없으면, 약속이 몰려 있어서 외로움이 극대화되는 것보다는 (약속이 쭉 있다가 약속 없는 날이 연속 4일이 되는 경우에, 외로움은 1의 제곱+ 2의 제곱+ 3의 제곱+ 4의 제곱이 된다.) 기분의 제곱을 해서 우울함 수치를 구하니까 약속을 최대한 분배하는 게 좋다 !

일단은 약속 분배..를 생각하기에 앞서서 약속을 최대한 몰아봤다. 기분이 -1로 가려고 하면, 그 때 약속을 배치하는 식으로 했다.
그러면 기분이 0 미만으로 가는 날의 개수를 파악할 수 있다!
이것을 가지고, 우울함의 합이 최소가 되게 분배했다.

2 10
1 1 1

이라는 경우가 있다고 생각해보자.
1번 그림처럼 약속을 분배할 수도 있고, 2번 그림처럼 약속을 분배할 수도 있다.
1번 그림의 경우 우울함의 합은 (1^2 + 2^2+ 3^2+ 4^2+5^2+6^2)가 된다.
2번 그림의 경우 우울함의 합은 (1^2+2^2) * 3 이 된다.
2번 그림처럼 약속을 분배할 수 있도록 '외로운 시간을 최대한 나누기!' 아래의 코드를 짰다..!
N+1개 만큼 분배할 수 있는 위치(?)가 생기니까, 그 곳에 기분이 0 미만으로 가는 날을 모두 배치하는 식이다.
배치하고 나면 그때의 우울함을 ans에 모았다. 처음에는 1을 제곱해서 ans에 더하고, N+1개 만큼 분배하고 나면 2를 제곱해서 ans에 더하고...

코드

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

if sum(arr) >= M:  # 매일 행복할 수 있으면(기분이 마이너스로 안 가면)
    ans = 0
else:
    m = M  # 남은 방학
    mood = 0  # 기분
    idx = 0
    while m > 0:
        mood -= 1
        if mood <= -1:
            if idx < N:  # 기분이 0이고 약속 있으면 그 약속 배치하기
                mood = arr[idx]
                idx += 1
            else:
                break
        m -= 1  # 하루 더 지났다.
    cnt = m  # 우울한 날

    # 외로운 시간을 최대한 나누기 !
    ans = 0
    idx = 1
    jegop_hal_su = 1
    while idx <= cnt:
        for i in range(N + 1):
            if idx > cnt:
                break
            ans += jegop_hal_su ** 2
            idx += 1
        jegop_hal_su += 1


print(ans)