글 읽기 - 74%에서 WA를 받는데, 반례가 혹시 있을까요?

surung9898 4년 전 0

알고리즘 상으로는 다이나믹 프로그래밍을 이용해서,

볼륨을 변경할 수 있을 경우 2차원 dp 배열에 저장하는 방식으로 해봤습니다만... 어려움을 겪고 있습니다.

50줄 정도 밖에 되지 않는 코드라 찾기가 더 어려운 것 같습니다..

코드 상의 문제점이나, 반례 제시해주시면 감사하겠습니다.

#include <iostream>
#include <stdlib.h>

using namespace std;

int main()
{
	int i, n, s, m, *arr, **dp, no = 0;

	scanf("%d %d %d", &n, &s, &m);

	arr = (int*)malloc(sizeof(int) * n);
	dp = (int**)malloc(sizeof(int*) * (m + 1)); //2차원 배열 생성 중

	for (i = 0; i < n; i++)
	{
		dp[i] = (int*)calloc(n+1, sizeof(int));
		scanf("%d", &arr[i]);
	}

	for(i = n; i <= m; i++)
		dp[i] = (int*)calloc(n+1, sizeof(int));

	dp[s][0] = 1; //초기 볼륨

	for (i = 0; i < n; i++) //각 곡마다
	{
		for (int j = 0; j <= m; j++) //모든 범위를 확인해서
		{
			if (dp[j][i] && j - arr[i] >= 0) //특정 볼륨으로 줄일 수 있다면
				dp[j - arr[i]][i + 1] = 1; //다음 배열에 저장

			if (dp[j][i] && j + arr[i] <= m) //특정 볼륨으로 늘릴 수 있다면
				dp[j + arr[i]][i + 1] = 1; //다음 배열에 저장
		}
	}

	for (i = m; i >= 0; i--) //최댓값 찾기
	{
		if (dp[i][n]) //찾았당!
		{
			no = 1;
			printf("%d\n", i);

			break;
		}
	}

	if (!no) //못 찾았당!
		printf("-1\n");

	return 0;
}

djm03178 4년 전 1

dp에 할당된 포인터는 m+1개인데, 이보다 n이 크다면 17번째 줄에서 할당된 범위를 벗어난 곳에 메모리를 할당받으려고 하게 됩니다.

surung9898 4년 전 0

정말 감사합니다. 한 번에 다 처리하려는 강박증이 이런 사고를 불러올 줄은 몰랐습니다.

m+1보다 큰 n을 넣는 테스트케이스를 시도했었더라면... 그저 미숙할 따름입니다.

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

문제

문제

출처

ICPC

74%에서 WA를 받는데, 반례가 혹시 있을까요?

surung9898 4년 전 0

djm03178 4년 전 1

surung9898 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말