글 읽기 - 2624 7% 반례 질문입니다.

bw2218 6년 전 0

7%까지 맞고 틀리다고 나오네요! 반례 혹시 알 수 있을까요? 또는 어떤 로직이 틀렸을까요??

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
using namespace::std;
int memo[105][10005]; 
int T;
int k; 
struct state {
	int x;
	int y;
};
vector<state> vec;
bool cmp(state a, state b) {
	return a.x >= b.x;
}
int Coin(int index, int sum) { // index부터 시작하여 sum을 만드는 가짓수 반환
	if (memo[index][sum] != -1)
		return memo[index][sum];
	if (sum == 0)  // 돈을 다 사용 했다면
		return 1;
	if (index == k) // 더 이상 사용할 동전이 없을 때
		return 0;
	
	int total = 0;
	int m = T / vec[index].x; // 최대 사용 가능 개수
	for (int i = 0; i <= vec[index].y; i++) { // 0개 사용부터 k개 사용까지
		if (m < i) // 동전이 필요 이상으로 사용 될 경우
			break;
		total += (Coin(index+1, sum-(vec[index].x*i)));
	}
	return memo[index][sum] = total;
}
int main(void)
{
	freopen("input.txt", "r", stdin);
	memset(memo, -1, sizeof(memo));
	cin >> T; // 지폐의 금액
	cin >> k; // 동전의 가짓 수
	for (int i = 0; i < k; i++) {
		int p; int n;
		cin >> p >> n; // 동전의 금액, 개수
		state ns; ns.x = p; ns.y = n;
		vec.push_back(ns);
	}
	sort(vec.begin(), vec.end(), cmp); // 금액 순으로 정렬 ( 내림 차순)
	cout << Coin(0, T) << endl;
	return 0;
}

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

문제

문제

출처

ICPC

2624 7% 반례 질문입니다.

bw2218 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말