글 읽기 - 배열 크기에 따라 결과가 다릅니다

wwiiiii 8년 전 0

bool dp[2][36000]으로 크기를 잡으면 맞고, dp[2][25000]으로 크기를 잡으면 틀리고, dp[2][15700]으로 잡으면 런타임 에러가 나네요;

제 생각엔 어차피 dp[0][j+arr[i]]에서 j + arr[i]가 인덱스의 최고이니까 dp[2][SHIFT + 300 + 10]정도로 크기를 잡으면 될 것이라 생각했는데 왜 이런 결과가 나오는지 궁금합니다

#include <cstdio>
#include <cstring>
#define SHIFT (15100)
using namespace std;

int abs(int a){return a>0?a:-a;}
bool dp[2][36000]; // dp[i][j] == arr[0]~arr[i]로 j-SHIFT의 값을 만들 수 있는지 
int arr[35];
int a;

int main() 
{
	int b = 0, target;
	scanf("%d",&a);
	for(int i=0;i<a;i++) scanf("%d",&arr[i]);
	scanf("%d",&b);
	dp[0][arr[0]] = dp[0][0] = true;
	for(int i=1;i<31;i++)
	{
		for(int j=0;j<SHIFT;j++)
		{
			dp[1][j] |= dp[0][abs(j-arr[i])];
			dp[1][j] |= dp[0][j+arr[i]];
			dp[1][j] |= dp[0][j];
		}
		for(int j=0;j<SHIFT;j++)dp[0][j]|=dp[1][j];
	}
	for(int i=0;i<b;i++)
	{
		scanf("%d",&target);
        if(dp[1][target] == true) printf("Y ");
	    else printf("N ");
	}
	
	return 0;
}

ntopia 8년 전 2

확인하려는 추의 무게에 대한 제한은 딱히 없긴 하네요

확인하려는 추의 무게가 25000을 넘어서 잘못된 곳을 접근하는 바람에 런타임에러가 나거나 틀리는게 아닐지요...

wwiiiii 8년 전 0

오 그렇네요...target = max(target, 30 * 500 + 10)으로 제한 걸어주니까 되네요;;

당연히 범위 내일줄 ㅠㅠ

joonas 8년 전 0

ㅎㅎ저도 이것때문에 계속 틀려서.... 후.. ㅋㅋㅋㅋㅋ

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

문제

문제

출처

ICPC

배열 크기에 따라 결과가 다릅니다

wwiiiii 8년 전 0

ntopia 8년 전 2

wwiiiii 8년 전 0

joonas 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말