글 읽기 - 반례좀 부탁드립니당 ㅎㅎ;

kkyung0321 5년 전 0

질문 게시판 반례도 잘 나오는데 어디서 틀린지 모르겠습니다. ( _ _ )

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>

#define MAX 10002

int n, k;
int arr[101];
int cache[10001];

int dp(int,int);

int min(int a, int b) {
	return a <= b ? a : b;
}

int main(void) {

	std::cin >> n >> k;
	
	for (int i = 1; i <= n; i++) {
		std::cin >> arr[i];
	}

	for (int i = 0; i <= 10001; i++) {
		cache[i] = MAX;
	}
	int temp = dp(k, n);

	if (temp >= MAX)
		std::cout << -1;
	else
		std::cout << temp;


	return 0;

}

int dp(int sum,int cnt) {
	if (sum < 0)
		return MAX;

	if (sum == 0)
		return 0;

	int &ref = cache[sum];

	if (ref < MAX)
		return ref;

	for (int i = cnt; i >= 1; i--) {
		ref = min(ref, dp(sum - arr[i], i)+1);
	}

	return ref;

}

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

문제

문제

출처

ICPC

반례좀 부탁드립니당 ㅎㅎ;

kkyung0321 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말