BOJ 2451(모둠) 풀이

이미지를 누르면 문제로 이동합니다

이 문제를 요약하면 N개의 수를 나열하고, 연속된 수들로 모둠을 여러 개 만든다. (1개에서 N까지 다양하게)

그때, 각 모둠끼리는 모두 직접 연결되어 있어야 하는데 그렇지 않을 경우, 부족한 개수만큼 점수가 오른다. 또 자신의 모둠이 아닌 다른 모둠과 연결되어 있을 때에도 개수만큼 점수가 오른다. 이때 점수의 최솟값을 찾는 문제이다.

문제에 있는 예시

이 그림으로 예를 들면, 이 그림에는 모둠이 2개가 존재하는데, 왼쪽에 있는 모둠은 내부에서 부족한 간선의 수는 3개가 되고, 오른쪽에 있는 모둠은 1개, 두 모둠을 잇는 간선 1개로, 이 그림은 5점을 가진다.

 

이 문제의 N의 범위는 2000 이하 이기 때문에 완전탐색은 통하지 않는다.

그럼 어떻게 풀 수 있을까?

 

누적 합과 dp 를 사용하면 풀 수 있다.

dp [i]를 모둠의 가장 오른쪽 점의 번호가 i 일 때 점수의 최솟값이라고 정의하자.

그럼 이제 dp [i]를 구해야 되는데 이건 어떻게 구할 수 있을까?

 

이는 N의 범위와 구해야되는 점수의 계산방법을 생각해 보면 된다.

 

N의 범위는 앞에서 2000까지라고 했으므로, N^2 까지는 무난하게 돌 수 있다. 그러니 i번호가 오른쪽 끝 점이라고 할 때, i보다 적은 점을 가장 왼쪽으로 반복을 통해 정해주면 모둠의 구간을 잡을 수 있다.

그다음 점수 계산 방법인데, 

점수는 모둠에 속해 있는 점의 수를 X라고 할 때, ( X * ( X - 1 ) ) / 2 개의 모둠 안에 존재해야 되는데, 그렇지 않은 개수만큼을 구해줘야 하고, 자신의 모둠 이외에 연결된 간선들도 더해줘야 한다.

이걸 앞에서 모둠의 구간을 잡는 것과 합쳐보면, 각 구간의 모둠마다 모둠 안에서 부족한 간선 수와 외부와 연결된 간선 수를 구해주고, 최솟값을 구하면 dp [i]를 구할 수 있다.

 

이때 누적합을 사용한다.

간선 정보를 입력받을 때, 2차원 배열에 저장한 뒤, 2차원 누적합을 만들어 준다.

2차원 누적합은 0,0부터 i, j까지 모두 더한 값을 나타낸다.

2차원 누적합에서 i점부터 j점까지의 구간합을 구하려면 ( i < j), 

PS [j][j] - PS [i - 1][j] - PS[j][i - 1] + PS[i - 1][i - 1]

이렇게 해주면 구할 수 있다.(이 정도는 혼자 생각하는 걸 추천한다)

 

이렇게 누적합을 사용해 구간에 있는 간선의 개수를 구했다면, 구간의 개수에다가 빼주면 된다. 

그리고 외부 간선 같은 경우, 자신의 모둠의 왼쪽에 있는 점들 중 외부의 간선을 아까처럼 누적합을 사용해 구해주면 된다.

 

왼쪽만 더해주는 이유는, 양쪽 모두 더했을 경우, 다른 모둠에서도 그 간선을 더할 수 있어 최솟값을 계산하는데 반례가 생길 수 있다. 그래서 처음부터 왼쪽만 더해줘서 반례가 생기지 않도록 한다.

이렇게 하면 dp [i]를 구할 수 있고, 최종적으로 dp [n]의 값이 최솟값이 된다. 

하지만 이 문제는 모둠 당 점의 수까지 출력해야 하는 문제이므로,

앞서 dp [i]의 최솟값을 갱신할 때마다 해당 그룹의 구간을 저장해 주고, 역추적을 통해 구해주면 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct nd{
	ll s,e;
};
ll n,inp,inf=4000*3000 + 100;
ll et[3002][3002],inps[3002][3002];
ll dp[3002];
vector<ll>aps;
vector<nd>answer;
ll INPS(ll i,ll j){
	return inps[j][j]-inps[i-1][j]-inps[j][i-1]+inps[i-1][i-1];
}
nd path[3002];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n;
	fill(dp,dp+3002,0);
	fill(path,path+3002,(nd){0,0});
	for(int i=0;i<3002;i++){
		fill(et[i],et[i]+3002,0);
		fill(inps[i],inps[i]+3002,0);
		
	}
	for(int i=0;i<n;i++){
		while(1){
			cin >> inp;
			if(inp==0)break;
			if(i+1==inp)continue; 
			et[i+1][inp]=1;
			et[inp][i+1]=1;
		}
	}
	aps.push_back(0);
	for(int i=1;i<3002;i++){
		ll V=0;
		for(int g=1;g<3002;g++){
			V+=et[i][g];
		}
		aps.push_back(aps[i-1]+V);
	}
	for(int i=1;i<=n;i++){
		for(int g=1;g<=n;g++){
			inps[i][g]=inps[i-1][g]+inps[i][g-1]-inps[i-1][g-1]+et[i][g];
		}
	}
	ll mn=0,N,Inps,cost;
	for(int i=1;i<=n;i++){
		mn=inf;
		for(int g=0;g<i;g++){
			N=i-(g+1)+1;
			Inps=INPS(g+1,i);
			cost=(N*(N-1) - Inps)/2 + (inps[i][i]-inps[g][i] - Inps);
			//cout << cost << ' ' << dp[g]<< '\n';
			if(mn>cost+dp[g]){
				path[i]={g+1,i};
				mn=cost+dp[g];
			}
			
		}
		dp[i]=mn;
	}
	//for(int i=0;i<=n;i++){
	//	cout << dp[i] << ' ';
	//}
	//cout << "\n";
	ll ans=dp[n],idx=n,MS=0,S,E;
	while(idx>0){
		answer.push_back(path[idx]);
		idx=path[idx].s-1;
	}	
	//cout << ans << "\n";
	cout << ans << "\n";
	cout << answer.size() << ' ';
	for(int i=answer.size()-1;i>=0;i--){
		cout << answer[i].e-answer[i].s+1 << ' ';
	}
	
}