글 읽기 - 동전문제 질문드립니다 ㅠㅠ

heogj123 8년 전 0

2293번 동전 1이랑 비슷하게 풀었는데요

우선 인풋들 퀵소트로 정렬하고 작은것부터 인풋을 받도록했어요

그리고 가지고있는 동전으로 나누어떨어지는 금액인경우 1로 초기화하여 다음 DP에 적용하도록하였고요..

어느 테스트케이스에서 걸리는지를 모르겠네요 ㅠㅠㅠ

---------------------------------------------------------------------------------------------------------------------------------------

다시 수정하여 코드를 짜봤습니다.

큰틀은 그대로이고 왠만한 인풋 다 한번씩 넣어봤다고 생각하는데 어디서 틀린건지..

고수님들 지나가는길에 한번씩만이라도 봐주고 가세요 ㅠㅠㅠ

#include <iostream>
#include <stdio.h>

using namespace std;

long long arr[1100];
long long dp[100100];
int n,k;

void mkdp()
{
	dp[0] = 0;
	long long minimum =	 1109000000;
	for(int i=0;i<n;i++)
	{
		dp[arr[i]] = 1;
		for(int j=arr[i];j<=k;j++)
		{
			if(dp[j-arr[i]] != 0)
				dp[j] = dp[j-arr[i]] + 1;
 		}
		if(dp[k] != 0)
			minimum = minimum>dp[k]?dp[k]:minimum;
	}
	int e = 10;
	if(dp[k] == 0 || minimum == 1109000000){
		printf("%d",-1);
		return ;
	}
	cout << minimum;
}

void quickSort(int lo,int hi)
{
	int i=lo,j=hi;
	int h;
	int x = arr[(lo+hi)/2];

	do{
		while(arr[i] < x)i++;
		while(arr[j] > x)j--;

		if(i<=j)
		{
			h = arr[i];
			arr[i] = arr[j];
			arr[j] = h;
			i++;j--;
		}
	}while(i<=j);

	if(lo<j)quickSort(lo,j);
	if(i<hi)quickSort(i,hi);
}


int main()
{
	cin >> n >> k;
	for(int i=0;i<n;i++) cin >> arr[i];
	quickSort(0,n-1);
	mkdp();
}

whgusfud 8년 전 1

3 15

input으로 넣으면 1이 나오네요..... -1이 나와야 할텐데????????

whgusfud 8년 전 0

이 문제에대해 힌트를 좀 드리자면,
일반적인 문제들과 다르게, 이 문제에서는 큰거부터 꽉꽉 채워넣었을 때가 답이 아닐 수 있습니다.
예제로 나온 3 , 15, 1 , 5, 12를 보아도 알 수 있는데,
12 1 1 1 = 15 (4) > 5 5 5 = 15 (3)

저는 다음과 같은 방식으로 했습니다.

1, dfs 방식으로 완전탐색.

2. dp로 시간단축

void func(int iterator, int remain_k, int count){
	int i,j;

	if(min_count <= count)
		return;

	for(i = iterator; i < n; i++){
		int cmp_value = remain_k - value[i];
		//printf("remain_k : %d , n[i] : %d , cmp_value : %d , count : %d\n",remain_k,value[i],cmp_value,count+1);

		if(cmp_value > 0){
			if(func_arr[i][cmp_value] == -1 || func_arr[i][cmp_value] > count+1){
				func_arr[i][cmp_value] = count+1;
				func(i,cmp_value, count+1);
			}
		}
		else if(cmp_value == 0){
			if(min_count > count+1){
				min_count = count+1;
			//	cout << "update!!!" << endl;
			}
		}
	}
}

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

문제

문제

출처

ICPC

동전문제 질문드립니다 ㅠㅠ

heogj123 8년 전 0

whgusfud 8년 전 1

whgusfud 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말