글 읽기 - 반례를 찾는다면 당신도 카이조쿠오

gusdnr9875 3년 전 0

dp 사용해서 풀었습니다.

반례가 보이지 않아서 글 올립니다.

찾아주시면 너무 감사하겠습니다. ㅠㅠ

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a = 0, b = 0;
int sinker[31] = { 0, };
int arr[7] = { 0, };
int dp[40001][31];


int solved(int weight, int current) {
	if (weight == 0)
		return 1;
	if (current > a)
		return 0;

	int &ret = dp[weight][current];
	if (ret != -1)
		return ret;
	ret = 0;
	for (int i = current; i <= a; i++) {

		if (sinker[i] <= weight) {
			ret = solved(weight - sinker[i], i + 1);
		}
		ret = max(ret, solved(weight, i + 1));
		ret = max(ret, solved(weight + sinker[i], i + 1));
		return ret;
	}

	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> a;
	for (int i = 1; i <= a; i++)
		cin >> sinker[i];

	cin >> b;
	for (int i = 1; i <= b; i++) {
		int temp;
		cin >> temp;
		memset(dp, -1, sizeof(dp));

		
		if (solved(temp, 1))
			cout << 'Y';
		else
			cout << 'N';

		if (i != b)
			cout << ' ';
	}
	cout << endl;
	return 0;

}

qktkzpal3301 3년 전 2

배열의 범위가 40000인데, 40000인 무게의 구슬 쪽에 추를 놓으면 배열의 범위를 초과하게 되지 않을까요?

gusdnr9875 3년 전 1

와 미쳤다.. 너무 감사합니다. 형님 오늘부터 해적왕하십시오.

gusdnr9875 3년 전 1

앗 그래도 반례가 있네요

gusdnr9875 3년 전 2

자문자답: 재귀 호출부분이 이상합니다. weight - sinker[i]가 음수가 나올때도 고려하여 결과를 유도해야 합니다.

qktkzpal3301 감사합니다.

for (int i = current; i <= a; i++) {

		
		ret = solved(abs(weight - sinker[i]), i + 1);
		ret = max(ret, solved(weight, i + 1));
		ret = max(ret, solved(weight + sinker[i], i + 1));
		return ret;
	}

qktkzpal3301 3년 전 1

네 저는 음수일 경우 고려해서, offset을 줘서 풀었습니다. 고생하셨습니다.

#include <bits/stdc++.h>
using namespace std;
const int offset = 60000;
int a, b, t;
int w[31];
int dp[120001][31];
int dyn(int weight, int idx) {
    if (weight == offset)
        return 1;
    if (idx > a)
        return 0;

    int& ret = dp[weight][idx];
    if (ret != -1)
        return ret;
    ret = 0;
    ret = dyn(weight - w[idx], idx + 1);
    ret = max(ret, dyn(weight, idx + 1));
    ret = max(ret, dyn(weight + w[idx], idx + 1));
    return ret;
}

int main() {
    scanf("%d", &a);
    for (int i = 1; i <= a; i++) scanf("%d", &w[i]);
    scanf("%d", &b);
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= b; i++) {
        scanf("%d", &t);
        printf("%c", dyn(offset + t, 1) ? 'Y' : 'N');
        if (i != b) printf(" ");
    }
    return 0;

}

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

문제

문제

출처

ICPC

반례를 찾는다면 당신도 카이조쿠오

gusdnr9875 3년 전 0

qktkzpal3301 3년 전 2

gusdnr9875 3년 전 1

gusdnr9875 3년 전 1

gusdnr9875 3년 전 2

qktkzpal3301 감사합니다.

qktkzpal3301 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말