백준 21757, 나누기

개요

문제 링크
골드 2, DP, Bisect
나눈 부분 수열의 합이 모두 같도록 수열을 4덩이로 나누기

---

접근

DP로 푸는 방법과 이분탐색으로 푸는 방법이 있는데 일단 생각나는건 이분탐색 뿐이라 일단 이분탐색을 사용했다. 둘 다 설명해볼 테니 천천히 뜯어보자.

이분탐색

1. 크게 어렵지 않다. 누적합이 S인 인덱스를 map에 벡터 형태로 저장한다. 인덱스는 순차적으로 저장될테니 모든 벡터는 오름차순이다.
2. 어떤 인덱스가 전체 합의 절반 M이면, 그 앞과 뒤에 존재하는 인덱스 중에서 누적합이 M/2, M/2×3인 인덱스를 찾아줘야 한다. 그런데 앞서 map에 인덱스의 벡터를 오름차순 형태로 저장했으니, 개수를 찾기 위해 lower, upper bound를 활용하면 된다.
3. 따라서 아래처럼 해준다.

    왼쪽 개수 = map[M/2].find(i-1)
    오른쪽 개수 = map[M/2*3].find(n) - map[M/2*3].find(i+1)
    answer += 왼쪽 * 오른쪽

   왼쪽은 i보다 작아야 하니까 i-1의 upper bound를 해준다. 오른쪽은 i보다 크고 n보다 작아야 하니까 i+1의 lower bound부터 n의 lower bound까지 개수를 구한다.

조합론

1. DP보다는 조합론에 가깝고 26156 나락도 락이다 문제와 똑같이 생각하면 된다. 앞에서부터 보자. 4분할 지점을 q1,q2,q3라고 하고 이 세 인덱스를 구성한다고 할 때, q2는 앞에 있는 모든 q1을 선택할 수 있고, q3는 앞에 있는 모든 q2를 선택할 수 있다.
2. 겹치는 것을 걱정할 수 있는데 겹치지 않는다. 왜냐? 서로 다른 q는 중복적으로 선택되지 않기 때문인데, 순차적으로 앞에서부터 모든 누적합을 탐색할 것이므로 한 번 선택한 q3,q2,q1을 다시 선택할 일은 없다.
3. 이 방법은 알기만 하면 단순한데 바로 생각하기가 꽤 어렵다. 잘 이해가 안된다면 이분탐색을 사용해보자.

---

Source code

// bisect
#include <bits/stdc++.h>
using namespace std;

#define N 100010
#define pb push_back
#define lower lower_bound
#define upper upper_bound
#define all(a) a.begin(),a.end()
using ld=long long;
using vec=vector<int>;
map <ld,vec> m;
ld s[N],n,x,ans;

int main() {
    cin.tie(0)->ios::sync_with_stdio(0);
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>x;
        s[i]=s[i-1]+x;
        m[s[i]].pb(i);
    }
    ld l,r;
    for (int i=2;i<n;i++) {
        if (s[i]*2!=s[n]) continue;
        if (s[i]%2) continue;
        auto &x=m[s[i]/2];
        l=(upper(all(x),i-1)-x.begin());
        auto &y=m[s[i]/2*3];
        r=(lower(all(y),n)-lower(all(y),i+1));
        ans+=l*r;
    }
    cout<<ans;
}

// combinatorics
#include <bits/stdc++.h>
using namespace std;

#define N 100010
using ld=long long;
ld s[N],n,x;
ld q1,q2,q3;

int main() {
    cin.tie(0)->ios::sync_with_stdio(0);
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>x;
        s[i]=s[i-1]+x;
    }
    for (int i=1;i<n;i++) {
        if (s[i]*4==s[n]*3)
            q3+=q2;
        if (s[i]*2==s[n])
            q2+=q1;
        if (s[i]*4==s[n])
            q1++;
    }
    cout<<q3;
}