글 읽기 - 반례를 알고 싶습니다.

adfsfsf 3년 전 0

원인은 알았지만 그 예시를 알고 싶습니다. 제가 정답 처리를 받기 위해 지운 코드는 주석처리한 38~41번 줄입니다. 해당 코드가 있을 때 틀리는 예시가 어떤 것이 있을지 알고 싶습니다.

#include <stdio.h>

void mergeSort(int p, int r);
void merge(int left, int mid, int right);

int num[10005], tmp[50005];

int main(void) {

	int n, k;

	int i, j;
	int dp[10005] = { 0 };

	scanf("%d %d", &n, &k);

	for (i = 0; i < n; i++)
		scanf("%d", &num[i]);

	mergeSort(0, n - 1);
	//num을 큰 수가 앞으로 오도록 정렬한다.

	for (i = 0; i < n; i++)
	{
		if (num[i] > k)
			continue;
		if (num[i] == num[i - 1])
			continue;
		dp[num[i]] = 1;
		for (j = 1; j + num[i] <= k; j++)
		{
			if (dp[j] != 0)
			{
				if (dp[j + num[i]] == 0 || dp[j + num[i]] > dp[j])
					dp[j + num[i]] = dp[j] + 1;
			}
		}
        /*
        if(dp[k]!=0)
            break;
        */
	}

	if (dp[k] == 0)
		printf("-1\n");
	else
		printf("%d\n", dp[k]);

	return 0;

}

void mergeSort(int p, int r) {
	int check[50005][5];
	int ind, mid, maxind;
	ind = 0;
	check[ind][0] = p;
	check[ind][1] = r;
	check[ind][2] = -1;
	maxind = 0;
	while (ind >= 0)
	{
		if (check[ind][3] == -1)
		{
			if (check[ind][4] == -1)
			{
				mid = (check[ind][0] + check[ind][1]) / 2;
				merge(check[ind][0], mid, check[ind][1]);
				if (check[ind][2] != -1)
				{
					if (check[check[ind][2]][3] == ind)
						check[check[ind][2]][3] = -1;
					else
						check[check[ind][2]][4] = -1;
				}
				ind = check[ind][2];
			}
			else
			{
				ind = check[ind][4];
				continue;
			}
		}
		else if (check[ind][0] < check[ind][1])
		{
			mid = (check[ind][0] + check[ind][1]) / 2;
			check[maxind + 1][2] = ind;
			check[maxind + 1][1] = mid;
			check[ind][3] = maxind + 1;
			check[maxind + 1][0] = check[ind][0];
			maxind++;
			check[maxind + 1][2] = ind;
			check[maxind + 1][1] = check[ind][1];
			check[ind][4] = maxind + 1;
			check[maxind + 1][0] = mid + 1;
			maxind++;
			ind = check[ind][3];
		}
		else
		{
			if (check[check[ind][2]][3] == ind)
				check[check[ind][2]][3] = -1;
			else
				check[check[ind][2]][4] = -1;
			ind = check[ind][2];
		}
	}
}

void merge(int left, int mid, int right) {
	int i, j, k, l;
	i = left;
	j = mid + 1;
	k = left;

	/* 분할 정렬된 list의 합병 */
	while (i <= mid && j <= right) {
		if (num[i] >= num[j])
			tmp[k++] = num[i++];
		else
			tmp[k++] = num[j++];
	}
	if (i > mid) {
		for (l = j; l <= right; l++)
			tmp[k++] = num[l];
	}
	else {
		for (l = i; l <= mid; l++)
			tmp[k++] = num[l];
	}
	for (l = left; l <= right; l++) {
		num[l] = tmp[l];
	}
}


/*
1. 우선 입력받은 값에 해당하는 칸에 1을 넣는다.
2. 그 후, 가장 작은 값부터 확인하면서, 값이 있으면 현재 값을 더한 값을 체크한다.
*/

adfsfsf 3년 전 0

간단한 예시가 있었네요.

3 12

이 경우 주석을 취소하면 4*3=12라서 답이 3이 나오고 주석처리를 놔두면 10+2=12 때문에 답이 2가 나옵니다. 그러므로 답이 2가 되어야 하는데 3이 출력되는 예시가 생깁니다.

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

문제

문제

출처

ICPC

반례를 알고 싶습니다.

adfsfsf 3년 전 0

adfsfsf 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말