[2019 숭고한 캠프] 백준 17392 우울한 방학

문제 링크

https://www.acmicpc.net/problem/17392

17392번: 우울한 방학

 

모든 약속을 적절히 배치해서 우울함의 합을 최소로 만들면 됩니다.

 

어떤 약속의 기대행복값을 $H_i$라 하면, 그 약속이 있는 날을 포함해 $H_i+1$일 동안은 우울함을 느끼지 않습니다.

이를 수직선으로 생각해봅시다. 길이 $M$(방학의 일수)의 수직선 위에 길이가 서로 다른 수직선들(기대 행복값, 길이: $H_i+1$)을 적절히 배치하여 비어있는 구간의 길이에 따라 우울함의 합이 결정된다고 볼 수 있습니다.

 

길이 $M$의 수직선에 $N$개의 작은 수직선을 배치하면 빈 구간은 최대 $N+1$개가 나올 수 있고,

최소로 만들 수 있는 빈 구간 길이의 합은 $M - \sum_{i = 1}^N{(H_i + 1)}$ 입니다.

우울함 수치는 빈 구간이 길어질수록 제곱에 비례해서 커지게 됩니다.

따라서 직관적으로, 우울함의 합을 최소로 하기 위해선 빈 구간을 최대한 많게, 그 길이를 최대한 평균적으로 만들어야 최적이라는 걸 알 수 있습니다.

 

위 내용을 바탕으로 문제를 풀어봅시다.

수식으로 써놔서 뭔소린가 하겠지만 직접 수직선을 그려보면 쉽게 이해할 수 있습니다.

 

편의상 빈 구간 길이의 합을 $X$라 하겠습니다.

우선 $X \leq 0$ 이면 우울함을 느끼는 날이 없다는 뜻입니다.

그 외의 경우에 $X \div (N+1)$의 몫을 $q$, 나머지를 $r$이라 합시다.

$N+1$개의 빈 구간의 길이를 $q$로 둡니다. 그리고 그 중 $r$개의 구간에 길이를 1씩 더해주면 최대한 평균적으로 길이를 맞출 수 있게 됩니다.

 

빈 구간의 최적 길이를 결정했으니 답을 구할 수 있습니다.

길이가 $L$인 빈 구간에서 얻을 수 있는 우울함의 총합은 $$1^2+2^2+...+L^2 = \sum_{i=1}^L{i^2} = \frac{L(L+1)(2L+1)}{6}$$ 입니다.

 

모든 빈 구간에 대해 이를 반복문으로 구해도 되고, 아니면 모든 빈 구간의 길이는 $q$ 혹은 $q+1$임을 이용해 수식 하나로 쓸 수도 있습니다.

$$Ans= (\sum_{i=1}^{q+1}{i^2}) * r + (\sum_{i=1}^q{i^2}) * (N+1-r)$$

길이가 $q+1$인 구간이 $r$개, 길이가 $q$인 구간이 $N+1-r$개라는 뜻입니다.

 

 

정답 코드

반복문

#include <iostream>
using namespace std;
 
int n, m;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    
    int x;
    for (int i = 0; i < n; i++) {
        cin >> x;
        m -= (x + 1);
    }
    if (m <= 0) { cout << 0; return 0; }
    int q = m / (n + 1);
    int r = m % (n + 1);
    int ans = 0;
    for (int i = 0, j = 0; i < n + 1; i++, j++) {
        int val = (j < r) ? q + 1 : q;
        ans += val * (val + 1) * (2 * val + 1) / 6;
    }
    cout << ans;
}

 

수식

#include <iostream>
using namespace std;
 
int n, m;
int sum(int val) { return val * (val + 1) * (2 * val + 1) / 6; }
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    
    int x;
    for (int i = 0; i < n; i++) {
        cin >> x;
        m -= (x + 1);
    }
    if (m <= 0) { cout << 0; return 0; }
    int q = m / (n + 1);
    int r = m % (n + 1);
    int ans = 0;
    ans = sum(q + 1) * r + sum(q) * (n + 1 - r);
    cout << ans;
}