글 읽기 - 91%에서 계속 틀립니다 ㅠㅠ

jupiny 6년 전 0

d[]라는 배열을 하나 만들어 반복적 다이나믹 프로그래밍으로 문제를 풀어봤습니다.

왠만한 반례는 다 통과하는데 계속 91%에서 틀리네요 ㅠㅠ

혹시 이 알고리즘의 반례를 아시는 분은 답변 부탁드립니다.

#include <iostream>
#include <limits>
#include <vector>
using namespace std;

const int INF = numeric_limits<int>::max();

int main() {
	int n, k;
	vector<int> coin;
	cin >> n >> k;
	for(int i=0; i<n; i++) {
		int temp;
		cin >> temp;
		coin.push_back(temp);
	}
    
	vector<int> d(k+1, INF);
	int coin_size = coin.size();
	d[0] = 0;
	for(int i=1; i<=k; i++) {
		for(int j=0; j<coin_size; j++) {
			if(i-coin[j] >= 0 && d[i-coin[j]] != INF)
				d[i] = min(d[i], 1+d[i-coin[j]]);
		}
	}

	cout << d[k] << endl;
	return 0;
}

evenharder 6년 전 1

불가능할 때 -1 대신 2147483647이 출력됩니다.

jupiny 6년 전 0

아 INF일 때 -1로 출력한다는 것을 깜빡했네요 ㅠㅠ

정말 감사드립니다!!!!

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

문제

문제

출처

ICPC

91%에서 계속 틀립니다 ㅠㅠ

jupiny 6년 전 0

evenharder 6년 전 1

jupiny 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말