글 읽기 - 2294번 질문입니다.

piy0605 5년 전 0

먼저 코드가 지저분한 점 죄송합니다.

질문에 있는 모든 반례를 해보았으나 발견을 못했습니다.

1. coin벡터엔 동전의 가치(오름차순)
   vcnt벡터엔 동전의 최소개수를 저장했습니다.
   예를들어 vcnt[3][5]은 3번째 동전까지 포함해
   합 5를 만들 수 있는 최소 동전의 개수입니다.

2. 최소를 구하는 방법은,
   vcnt[3][5]를 구한다 했을 때,
   1> 동전의 가치가 목표합보다 클 시
vcnt[2][5]에서 가져옵니다
   2> 아니라면, 3번째 동전으로 만들 수 있는 경우의 수가 없다면 역시 vcnt[2][5]에서 가져오며
   3> 아니라면, 3번째 동전으로 만들 수 있는 모든 경우의 수, 각각 동전의 개수와 vcnt[2][5]를 비교하여
      최소값을 받습니다.

지적 부탁드립니다!

#include <iostream>
#include <vector>
#include <algorithm>
////////////////////////////////////
using namespace std;
////////////////////////////////////

////////////////////////////////////
int main() {
////////////////////////////////////
	int n, k;
	cin >> n >> k;
	
	vector<vector<int>> vcnt(n+1,vector<int>(k+1,-1)); // 
	vector<int> coin(n + 1, 0);
	
	for (int i = 0; i < n + 1; i++)vcnt[i][0] = 0;
	for (int i = 1; i < n + 1; i++) {
		cin >> coin[i];
	}
	sort(coin.begin(), coin.end());
	for (int i = coin[1]; i < k + 1; i++) {
		if (i%coin[1] == 0) {
			vcnt[1][i] = i/coin[1];
		}
	}

	for (int i = 2; i < n + 1; i++) {
		if (coin[i] <= k) {
			for (int j = coin[i]; j < k + 1; j++) {
				int tmp = 0;
				vcnt[i][j] = vcnt[i-1][j];
				while (tmp*coin[i] <= j)tmp++;
				tmp--;
				while (tmp > -1) {
					if (vcnt[i - 1][j - coin[i] * tmp] != -1) {
						if (vcnt[i][j]==-1 || vcnt[i][j] > tmp + vcnt[i - 1][j - coin[i] * tmp]) {
							vcnt[i][j] = tmp + vcnt[i - 1][j - coin[i] * tmp];
						}
					}
					tmp--;
				}
			}
		}
		else {
			for (int j = 1; j < k + 1; j++) {
				vcnt[i][j] = vcnt[i - 1][j];
			}
		}
	}

	cout << vcnt[n][k] << endl;

	vector<vector<int>>().swap(vcnt);
	vector<int>().swap(coin);	
////////////////////////////////////
	return 0;
}

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

문제

문제

출처

ICPC

2294번 질문입니다.

piy0605 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말