[백준 23076번] [수학] Trash Bins

Approach

Naive하게 생각해보면, 이 문제를 풀기 위해서는 주어지는 input에서 trash bin이 어디 있는지를 파악해야 한다.

그리고, 해당 trash bin을 기준으로 거리를 판단해주면 된다.

 

예를 들어 trash bin이 놓인 index가 1, 5라고 하면, 그 사이에 놓인 2,3,4는 가장 가까운 trash bin을 찾아나가게 되는데 이는 해당 trash bin 사이의 distance에 의해서 지배받게 된다. 만약 두 trash bin 사이의 거리가 짝수인 경우에는 2로 나누었을 때의 몫까지의 시그마 합의 2배이고, 홀수인 경우에는 거기에 몫을 한번 빼주면 된다.

 

Let trash bin's position is $x_i$ and $x_j$. (s.p.s $x_i < x_j$). Define that dis = d($x_i$, $x_j$).

If dis is odd, sum of trash bin distance within these two trash bin position is $(\sum\limits_{k = 1}^{\frac{dis}{2}} k) * 2= \frac{dis}{2} * (\frac{dis}{2} + 1) $

On the other hand, $\sum\limits_{k = 1}^{\frac{dis}{2}} k - \frac{dis}{2} = {(\frac{dis}{2})}^2$ 

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int main(void){
    fastio;
    int t;
    cin >> t;
    for(int i = 1; i <= t; i++){
        long long n;
        cin >> n;
        string s;
        cin >> s;
        vector<long long> bin;

        for(int i = 0; i < s.size(); i++){
            if(s[i] == '1'){
                bin.push_back(i);
            }
        }

        long long result = bin[0] * (bin[0] + 1) / 2 + (n - bin[bin.size() - 1] - 1) * (n - bin[bin.size() - 1]) / 2;

        for(int i = 0; i < bin.size() - 1; i++){
            long long front = bin[i];
            long long back = bin[i + 1];
            long long v = (back - front) / 2;
            if((back - front) % 2 == 1){
                result += v * (v + 1);
            }
            else{
                result += v * v;
            }
        }
        cout << "Case #" << i << ": " << result << "\n";
    }
    return 0;
}