구름LEVEL - 금은보화

문제

원소의 크기가 [1, 2000]에 속하는 정수이고, 길이가 \(N(1 \le N \le 250)\)인 수열 A가 주어진다.

위 수열을 두 개의 부분 수열 C, D로 나눌 때, 아래의 조건을 만족하는 C의 원소의 합 - D의 원소의 합의 차이의 최솟값과, 그 경우의 수를 구해야 한다.

• 원소의 값이 중복될 수 있는데, 같은 값이라도 다른 원소로 취급한다.
  (A가 [2, 2]로 주어진 경우, 최솟값은 0이고, 경우의 수는 2이다.)
• 원소의 합의 차이는 0 이상이어야 한다.
  (항상 C의 원소의 합이 D의 원소의 합 이상이어야 한다.)

이때, 경우의 수를 \(10^6\)으로 나눈 나머지를 출력해야 한다.

풀이

• \(dp(i)(j)\)를 \(A_i\)까지 분류를 완료했을 때 C의 원소의 합이 \(j\)인 경우의 수라고 정의하면 아래와 같은 점화식을 얻을 수 있다.

\[dp(i)(j)=dp(i-1)(j-A_i) + dp(i-1)(j)\]

• 해당 문제의 답은 원소의 합의 차이를 최소로 만드는 \(j\)에 대하여 \(dp(n)(j)\)이다.
  수열 A의 원소의 합을 T라고 할 때, j는 [t/2+t%2, t]에 속하며 j가 작을수록 합의 차이가 작아지기 때문에, 첫 번째 값부터 탐색하면 된다.
• 원소의 합의 최댓값은 \(250\times 2000=5 \times 10^5\)이므로, 전체 시간복잡도는 \(5 \times 10^5 \times 250 \approx 10^8\)이다.
• 모듈러 연산은 +, -, *에 대해 분배법칙이 성립하기 때문에, dp값을 계산할 때마다 모듈러까지 계산하는게 일반적이다.
  • 하지만, 테스트 케이스 9번의 경우, j가 \(10^6\)의 배수로 추정된다.
    (아래 코드 1의 26번째 줄의 조건문 없이 실행하게 되면, 9번 TC에서 WA를 받는다.
    이는 \(dp(i)(j)\)의 값이 \(10^6\)인데 답일 경우, 모듈러 연산에 의해 0으로 계산되고, 31번째 줄과 같이 dp의 값이 0이 아닌 경우에 대하여 출력할 답을 탐새가기 때문에 해당 값을 넘어가기 때문이다.
    따라서, dp의 값이 0이 아니라는 것을 나타내는 상태 정보를 따로 추가하여 해결할 수 있다.)
  • 아래 코드 1에서는 모듈러 연산을 적용하는 값의 기준을 \(10^9\)로 설정하여, TC 9번을 통과만 시킨 상태이다.
    즉, 답이 \(10^9\)인 TC에 대해서는 정답을 출력하지 못한다.
  • 코드 2는 값이 \(10^6\)의 배수라는 정보를 저장하는 not0 map을 사용하여 모든 TC를 커버하는 코드이다.

코드 1

#include<algorithm>
#include<iostream>
#include<vector>
#define MOD 1000000

using namespace std;

int tsum=0;
int getdif(int x){
	return 2*x-tsum;
}
int main() {
	int n;
	cin>>n;
	vector<int> ar(n, 0);
	for(int i=0;i<n;i++){
		cin>>ar[i];
		tsum+=ar[i];
	}
	vector<long long> dp(tsum+1, 0);
	dp[0]=1;
	for(int i=0;i<n;i++){
		vector<long long> tdp(dp);
		for(int j=ar[i];j<tsum+1;j++){
			tdp[j]=(dp[j-ar[i]]+dp[j]);
			if(tdp[j]>=1000000000) tdp[j]%=MOD;
		}
		dp=tdp;
	}
	for(int i=tsum/2+(tsum%2);i<tsum+1;i++){
		if(dp[i]!=0 && getdif(i)>=0){
			cout<<getdif(i)<<'\n'<<dp[i]%MOD;
			return 0;
		}
	}
}

코드 2

#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#define MOD 1000000

using namespace std;

int tsum=0;
int getdif(int x){
	return 2*x-tsum;
}
int main() {
	int n;
	cin>>n;
	vector<int> ar(n, 0);
	for(int i=0;i<n;i++){
		cin>>ar[i];
		tsum+=ar[i];
	}
	vector<long long> dp(tsum+1, 0);
	map<long long, int> not0;
	dp[0]=1;
	for(int i=0;i<n;i++){
		vector<long long> tdp(dp);
		for(int j=ar[i];j<tsum+1;j++){
			tdp[j]=(dp[j-ar[i]]+dp[j]);
			if(tdp[j]!=0 && tdp[j]%MOD==0) not0[j]=1;
			tdp[j]%=MOD;
		}
		dp=tdp;
	}
	for(int i=tsum/2+(tsum%2);i<tsum+1;i++){
		if(getdif(i)>=0){
			if(dp[i]!=0) cout<<getdif(i)<<'\n'<<dp[i]%MOD;
			else if(not0.find(i)!=not0.end()) cout<<getdif(i)<<'\n'<<0;
			else continue;
			return 0;
		}
	}
}

풀고나서

• 모듈러 값이 답에 영향을 주는 경우를 접하지 못해, 원인을 찾는데 시간이 많이 소요되었다.