BOJ 32114 : SoleMap

• 문제 링크 : boj.kr/32114
• 난이도 : G4
• 태그 : 누적합, 수학

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<ll> cap(n), arr(n+1);
    for(int i = 1; i < n; i++)
        cin >> cap[i];
    for(int i = 0; i < m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        arr[a] += c;
        arr[b] -= c;
    }
    for(int i = 1; i <= n; i++) {
        arr[i] += arr[i-1];
    }

    for(int i = 1; i < n; i++) {
        ll q = arr[i] / cap[i];
        ll r = arr[i] % cap[i];
        cout << (q+1)*(q+1)*r + q*q*(cap[i]-r) << "\n";
    }
    
    return 0;
}

---

풀이

각 도로별 차의 통행량은 누적합을 이용하여 구할 수 있다.

도로별로 차선에 차를 균등하게 분배하는 것이 최선이다.

 

균등하지 않은 경우가 최선이라고 해보자.

분배했을 때 가장 많은 차의 수를 a, 가장 적은 차의 수를 b라고 해보자. 이때 $a \ge b+2$이다.

$(a-1)^2 + (b+1)^2 = a^2 + b^2 + 2(b-a+1) < a^2 + b^2 \ \ (\because b-a+1 < 0)$

따라서 $b-a+1 < 0$인 경우, 그보다 더 최선인 경우가 항상 존재한다.

$b-a+1 \ge 0$여야 최선이므로 차를 균등하게 분배해야 한다.