BOJ 17670 - 난

문제 링크 : https://www.acmicpc.net/problem/17670 

문제 풀이

 문제에 존재하는 서브태스크이자 작은 경우인 N=2 인 경우를 살펴보자. 두 명이 각각 행복도가 절반이 되는 만족할 수 있는 위치가 $x_1, x_2$ 라고 하자. 그러면 일반성을 잃지 않고, $x_1<x_2$라고 하면, $x_1$에서 자르고 1번에게 왼쪽 조각
2번에게 오른쪽 조각을 주면 된다. 두 번째 사람은 $x_2$ 이후의 조각만 먹으면 되는데  $x_1<x_2$ 이기 때문에 얻는 조각이 원하는 조각을 포함하기 때문에 항상 만족한다. 

 각자 적당히 만족할 수 있게 나누어 주면 되며, DP 형태로는 표현이 안되고, 각자 좋아하는 부분이 있기 때문에 그리디로 해결이 가능해 보인다. N=2 인 경우를 확장해보자. 

 모든 N명의 사람에 대해서 각각 행복도를 만족하는 N개의 조각의 커팅 위치를 구해놓자. N명에 대해서 각각 N-1개의 커팅 위치가 나올 것이다. 그렇다면 첫 조각은 누구에게 가는 것이 좋을까? 그리디 적으로 생각하면 첫 커팅 위치가 가장 앞쪽인 사람에게 가는 것이 좋을 것이다.
 그렇다면 두 번째 조각은? 이미 받은 사람을 제외하고 두 번째 커팅 위치가 가장 앞쪽인 사람에게 가는 것이 좋을 것이다. 이때 N=2인 경우와 마찬가지로 두 번째 사람도 만족할 만한 크기의 (자신이 원하는 두 번째 조각을 포함하는 크기의) 조각을 받을 것이다. 이와 마찬가지로 i번째 조각은 아직 받지 않은 사람 중에서 i번째 커팅 위치가 가장 앞쪽인 사람에게 주면 모두가 만족하게 할 수 있다. 

 커팅 위치를 구하는 것은 $O(N^2)$ 에 가능하며 다양한 방법이 있고, prefix를 이용해서 편하게 진행했다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef double dl;
typedef pair<dl,dl> pdi;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> piii;
 
#define ff first
#define ss second
#define eb emplace_back
#define ep emplace
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
//cout<<fixed;
//cout.precision(12);
 
struct poi{
    pii p;
    ll idx;
};
 
vector<ll> x;
ll n,m;
ll mod=998244353;
string s;
string t;
ll arr[2020][2020];
ll pre[2020][2020];
pii cut[2020][2020];
ll sum[2020];
ll ansa[2020];
ll ansb[2020];
ll ansc[2020];
vector<poi> v[220022];
ll chk[1010101];
 
 
bool sf2(poi a,poi b){
    dl aa=a.p.ff;
    dl bb=a.p.ss;
    dl cc=b.p.ff;
    dl dd=b.p.ss;
    return aa/bb<cc/dd;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll i,j,k,a,b,c,d,e,f;
    cin>>n>>m;
 
      for(i=1;i<=n;i++){
          for(j=1;j<=m;j++){
              cin>>arr[i][j];
              sum[i]+=arr[i][j];
              arr[i][j]*=n;
              pre[i][j]=pre[i][j-1]+arr[i][j];
          }
      }
 
      for(i=1;i<=n;i++){
      ll fl=1;
          for(j=1;j<n;j++){
              while(pre[i][fl]<sum[i]*j){
                  fl++;
              }
              cut[i][j].ss=arr[i][fl];
              cut[i][j].ff=fl*cut[i][j].ss+sum[i]*j-pre[i][fl];
              poi x={cut[i][j],i};
              v[j].pb(x);
          }
      }
 
      for(i=1;i<n;i++){
          sort(v[i].begin(), v[i].end(),sf2);
          for(auto k:v[i]){
              if(chk[k.idx]) continue;
              chk[k.idx]=1;
              ansa[i]=k.p.ff;
              ansb[i]=k.p.ss;
              ansc[i]=k.idx;
              break;
          }
      }
      for(i=1;i<=n;i++){
          if(chk[i]==0) ansc[n]=i;
      }
 
      for(i=1;i<n;i++){
          cout<<ansa[i]<<' '<<ansb[i]<<'\n';
      }
      for(i=1;i<=n;i++)
          cout<<ansc[i]<<' ';
 
}