글 읽기 - 2294 동전2 틀린 경우의 수가 뭐가 있을까요ㅠ?

huhmin 8년 전 0

i번째 합을 못만드는 경우도 있어서 먼저 경우가 있는지

갱신해놓고 없는 경우를 제외하고 최소 동전의 개수로

다시 갱신합니다.

왠만한 경우의 수는 다 나오는데 자꾸 틀렸습니다가 뜨네요ㅠㅠ

다른 분들이 올려놓으신 질문에 대한 답으로 올라온 2 101 / 100, 1

이런거 돌려봐도 제대로 2가 나오는데 .. 뭐가 틀렸을까요ㅠㅠ?

틀린 경우 좀 찾아주세요...

#include <stdio.h>
#include <iostream>
using namespace std;
#define INF 987654321
void quicksort(int a[], int left, int right){
	if (left < right){
		int p = left;
		int pv = a[p];
		for (int i = left + 1; i < right; i++){
			if (a[i] < pv){
				p++;
				swap(a[i], a[p]);
			}
		}
		swap(a[p], a[left]);
		quicksort(a, left, p - 1);
		quicksort(a, p + 1, right);
	}
}
int main(){
	int n = 0;
	int k = 0;
	int val = 0;
	int arr[101];
	int brr[10001];
	freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++){
		scanf("%d", &val);
		arr[i] = val;
	}
	for (int i = 0; i < k + 1; i++)
		brr[i] = 0;
	brr[0] = 1;
	quicksort(arr, 0, n);
	for (int j = 0; j < n; j++){
		for (int i = 1; i < k + 1; i++){
			if (i < arr[j])
				continue;
			else{
				brr[i] = brr[i] + brr[i - arr[j]];
			}
		}
	}

	for (int i = 0; i < k + 1; i++){
		if (brr[i] != 0)brr[i] = INF;
	}
	for(int j = 0; j < n; j++)
		for(int i = 1; i < k + 1; i++){
			if (i < arr[j])
				continue;
			else if(i>=arr[j] && brr[j]!=0){
				if ((i%arr[j]) == 0){
					if (brr[i]>(i / arr[j]))
						brr[i] = i / arr[j];
				}
				else{
					if (brr[i] >(i / arr[j]) + (i%arr[j])){
						brr[i] = (i / arr[j]) + (i%arr[j]);
					}
				}
			}
		}
	if (brr[k] == 0) printf("-1\n");
	else
		printf("%d\n", brr[k]);
	return 0;
}

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

문제

문제

출처

ICPC

2294 동전2 틀린 경우의 수가 뭐가 있을까요ㅠ?

huhmin 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말