글 읽기 - 반례 찾습니다.

p_ce1052 3년 전 0

half까지 만들 수 있는 만큼 최대한 만들고

다시 하나씩 보면서 arr[i]를 더해 half를 넘어가는 수를 만들면 최댓값을 갱신하여

해당 최댓값으로 다시 구성하는 당을 만들어서 출력했는데 어디가 잘못됬나요?

#include<bits/stdc++.h>
using namespace std;
int total,half,ans,n;
bool dp[305][100005];
int arr[305];
int idx[305];
void solve(int cur){
	int cnt = 0;
	vector<int>ret;
	for(int i=cur; i>=1; i--){
		if(dp[i-1][ans-arr[i]]){
			cnt++;
			ret.push_back(idx[i]);
			ans-=arr[i];
		}
	}
	cout<<cnt<<'\n';
	sort(ret.begin(),ret.end());
	for(int x : ret) cout<<x<<" ";
	return;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	vector<pair<int,int> >vv(n);
	for(int i=0; i<n; i++){
		cin>>vv[i].first;
		vv[i].second = i+1;
	}
	sort(vv.begin(),vv.end());
	reverse(vv.begin(),vv.end());
	
	for(int i=0; i<vv.size(); i++){
		arr[i+1] = vv[i].first;
		idx[i+1] = vv[i].second;
	}
	
	dp[0][0] = 1;
	for(int i=1; i<=n; i++) total+=arr[i];
	half = total/2;
	
	if(total==0){
		assert(0);
		return 0;
	}
	for(int i=1; i<=n; i++){
		for(int j=half; j>=arr[i]; j--){
			if(j-arr[i]>=0 && dp[i-1][j-arr[i]]) dp[i][j]|=dp[i-1][j-arr[i]];
			dp[i][j]|=dp[i-1][j];
		}
	}
	
	for(int i=1; i<=n; i++){
		for(int j=0; j<=half; j++){
			if(dp[i-1][j] && j+arr[i]>half) ans = max(ans,j+arr[i]);
		}
	}
	
	for(int i=1; i<=n; i++){
		for(int j=0; j<=half; j++){
			if(dp[i-1][j] && j+arr[i]>half){
				if(j+arr[i]==ans){
					solve(i);
					return 0;
				}
			}
		}
	}
}

byeongkeunahn 3년 전 1

반례입니다.

20 19 18 17

-> should print {2,3,4}, but prints {1,2}

p_ce1052 3년 전 0

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 찾습니다.

p_ce1052 3년 전 0

byeongkeunahn 3년 전 1

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말