글 읽기 - 2294번 질문 있습니다 ㅠㅠ

Glitterlance 5년 전 0

지금까지 질문 올라왔던 테스트 케이스들을 넣어도 다 맞게 나오는데

도대체 어디서 틀렸는지 모르겠습니다 ㅠㅠ

이거는 정말 못 풀겠는데 도와주실 수 있으신가요 ㅠㅠ

일단 제가 풀은 방식은 이렇습니다.

1) 동전 종류 1개로 만들 수 있는 경우들 다 초기화 하고

2) 처음부터 다시 돌면서 더 적은 개수로 만들 수 있는지 확인

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int dp[10005];

void find(vector<int> &coin_set,int coin_num,int coin_dest) {
	for (int i = 0; i < coin_num;i++) {
		for (int j = coin_set[i]; j <= coin_dest;j += coin_set[i]) {
			if (dp[j] == -1 || dp[j] > j / coin_set[i]) {
				dp[j] = j / coin_set[i];
			}
		}
	}
	for (int i = 0; i < coin_num;i++) {
		for (int j = coin_set[i] + 1; j <= coin_dest;j++) {
			if (dp[i] != -1 && dp[j] > dp[j-coin_set[i]] + 1) {
				dp[j] = dp[j - coin_set[i]] + 1;
			}
		}
	}
	printf("%d\n",dp[coin_dest]);
}

int main() {
	int coin_num, coin_dest;
	int coin_temp;
	vector<int> coin_set;
	scanf("%d %d",&coin_num,&coin_dest);
	for (int i = 0; i < coin_num;i++) {
		scanf("%d",&coin_temp);
		coin_set.push_back(coin_temp);
	}
	sort(coin_set.begin(), coin_set.end());
	memset(dp, -1, sizeof(dp));
	find(coin_set,coin_num, coin_dest);

	return 0;
}

djm03178 5년 전 0

19번째 줄이 왜 dp[i]인지 모르겠습니다.

2 7
2
5

Glitterlance 5년 전 0

헉...

고쳐보겠습니다 ㅠ

Glitterlance 5년 전 0

해결했습니다. 감사합니다!!!

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

문제

문제

출처

ICPC

2294번 질문 있습니다 ㅠㅠ

Glitterlance 5년 전 0

djm03178 5년 전 0

Glitterlance 5년 전 0

Glitterlance 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말