글 읽기 - 45%에서 계속 틀립니다 ㅠㅠ

jupiny 6년 전 1

다이나믹 프로그래밍을 이용해 풀었는데, 계속 45%에서 에러가 발생하네요 ㅠㅠ

남아있는 추를 모두 사용해도 절대 구슬의 무게를 만들 수 없을 때는 false를 반환하도록 예외처리를 하였는데 어떤 반례가 있는 걸까요??

답변주시면 감사하겠습니다!

dp(idx, state): weight[idx]에서 weight[n-1] 까지의 추를 이용하여 state 값을 만들 수 있는지의 여부를 반환하는 함수

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

vector<int> weight;
vector<int> ball;
int n, m;
const int MAX_WEIGHT = 500;
const int MAX_N = 30;
int cache[MAX_N+1][MAX_N*MAX_WEIGHT+1];

int dp(int idx, int state) {
	if(state > MAX_WEIGHT * (n-idx))
		return 0;
	if(state == 0)
		return 1;
	if(state < 0)
		return 0;
	if(idx == n)
		return 0;
	int &ret = cache[idx][state];
	if(ret != -1)
		return ret;
	ret = 0;
	if(dp(idx+1, state) || dp(idx+1, state + weight[idx]) || dp(idx+1, state - weight[idx])) {
		ret = 1;
	}
	return ret;
}

int main() {
	cin >> n;
	for(int i=0; i<n; i++) {
		int a;
		cin >> a;
		weight.push_back(a);
	}
	cin >> m;
	for(int i=0; i<m; i++) {
		int a;
		cin >> a;
		ball.push_back(a);
	}

	memset(cache, -1, sizeof(cache));

	for(int i=0; i<m; i++) {
		int ret = dp(0, ball[i]);
		if(ret == 1)
			cout << "Y ";
		else
			cout << "N ";
	}
	cout << endl;
	return 0;
}

ho94949 6년 전 1

18-19번째 라인을 유심히 보시기 바랍니다.
과연 현재까지의 무게의 합이 음수라고 해서, 전체 원하는 무게를 만들지 못할까요?

jupiny 6년 전 0

아 제가 잘못 생각하고 있었네요 ㅠㅠㅠ

제가 생각한 알고리즘을 제가 잘못 이해하고 있었네요.

말씀해주신대로 18-19번째 줄 코드를 제거하고 14번째 줄 코드에도 음수 최솟값에 대한 조건을 추가하였더니 바로 해결됬어요!

정말 감사드립니다 :D

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

문제

문제

출처

ICPC

45%에서 계속 틀립니다 ㅠㅠ

jupiny 6년 전 1

ho94949 6년 전 1

jupiny 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말