글 읽기 - 신이시여... 제발 반례를 찾아주세요.

ndb796 6년 전 0

문제에서 요구하는 대로 잘 짰다고 생각하고 뿌듯해하고 있었으나... 특정 테스트 케이스에서 틀리다고 나옵니다.

제발 중생에게 반례를 알려주십시오...

#include <iostream>
#define MAX 1000001

using namespace std;

int a[1001];
int d[MAX];

int main(void) {
	int n;
	cin >> n;
	d[0] = 1;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	// 뒤에서 부터 만들 수 있는 모든 경우 체크 
	for(int i = 0; i < n; i++) {
		for(int j = MAX - 1; j >= a[i]; j--) {
			if(d[j - a[i]] == 1) {
				d[j] = 1;
			}
		}
	}
	for(int i = 1; i < MAX; i++) {
		if(d[i] == 0) {
			cout << i;
			break;
		}
	}
	return 0;
}

atomzeno 6년 전 1

MAX가 너무 작네요...게다가 dp로 풀리는지 의문인데..?

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144

에다 524288로 979번 정도 넣으면...최소한 513802239까지는 만들 수 있...어요..DP로 못 푸는 문제중 하나

ndb796 6년 전 0

그... 그렇군요! 감사합니다!

ndb796 6년 전 0

조금 고민해보니 DP를 쓸 필요가 없네요...!

단순히 정렬 이후에 각 원소를 더해보는 것만으로도 Optimal한 해를 찾을 수 있다는 걸 깨달았습니다...

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

문제

문제

출처

ICPC

신이시여... 제발 반례를 찾아주세요.

ndb796 6년 전 0

atomzeno 6년 전 1

ndb796 6년 전 0

ndb796 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말