글 읽기 - 60%에서 막힙니다... 반례가 어떻게 될까요

pupafafa 4년 전 1

채점 도중 60%까지는 이상없는데 60퍼를 넘어서는 순간 틀린 케이스가 있나봐요..

반례를 찾고싶은데 도저히 못찾겠습니다..

4일째 붙들고 있어요 ㅠㅠ

코딩 고수님들 혹시 눈에 보이는 반례가 있을까요..

#include<stdio.h>
#define max(a,b)((a)>(b)?(a):(b))
int main() {
	int x;// 차례로 목표금액
	int coin_value[5] = { 0,1,5,10,25 };
	int coin_amount[5] = { 0, };
	scanf("%d", &x);
	for (int i = 1; i <= 4; i++)
		scanf("%d", &coin_amount[i]);
	int dp[5][10001] = { 0, };
	int save_k[5][10001] = { 0, };
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= x; j++) {
			for (int k = 1; k <= coin_amount[i]; k++) {
				if (j >= coin_value[i] * k) {
					if (dp[i - 1][j] < dp[i - 1][j - coin_value[i] * k] + coin_value[i] * k ) {// 새롭게 갱신 된 경우 
						if (dp[i][j] == dp[i - 1][j - coin_value[i] * k] + coin_value[i] * k) break;
						dp[i][j] = dp[i - 1][j - coin_value[i] * k] + coin_value[i] * k;
						for (int p = 1; p < i; p++) {
							save_k[p][j] = save_k[p][j - coin_value[i] * k]; //해당 가격을 새 동전으로 대체
						}
						save_k[i][j] = save_k[i][j - coin_value[i] * k] + k;
					}
					//(1,51) (1,46)
					else {
						dp[i][j] = max(dp[i - 1][j], dp[i][j]);
					//	save_k[i][j] = save_k[i][j - 1];
					}
				}

				else {
					dp[i][j] = max(dp[i - 1][j], dp[i][j]);
					//save_k[i][j] = save_k[i][j - 1];
				}
			}
			if (dp[i][j] == 0)	dp[i][j] = dp[i - 1][j];
		}
	}
	for (int i = 0; i <= 4; i++) {
		for (int j = 0; j <= x; j++) {
		//	printf("%2d ", dp[i][j]);
		}
	//	printf("\n");
	}
	if (dp[4][x] != x) {
		printf("0 0 0 0\n");
		return 0;
	}
		for (int j = 1; j <= 4; j++) {
			printf("%d ", save_k[j][x]);
		}
	

}

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

문제

문제

출처

ICPC

60%에서 막힙니다... 반례가 어떻게 될까요

pupafafa 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말