白駿2294

1564 ワード
boj テキストリンク
https://www.acmicpc.net/problem/2294

3時間もかき回した.それでも解決できず、よくわからなかったので、グーグルを試してみたら、次のように編めばいいと言っていました.
ダイナミックプログラミング(dynamic programming)で解決すればいいそうです.
ダイナミックプログラミングについて、彼が書いた文章を読んでみましょう.https://hongjw1938.tistory.com/47
これは他の人が制定したアルゴリズムの設計方法です.これも読んでみよう
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=occidere&logNo=220794872664
コードに従って歩いて、見ながら理解します.
成功コード:
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

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

int main() {
	int N, K;
	int dp[10001];
	int coin[101];
	
	dp[0] = 0;
	for (int i = 1; i < 10001; i++) {
		dp[i] = 100001;
	}

	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++) {
		scanf("%d", &coin[i]);
		for (int j = coin[i]; j <= K; j++) {
			dp[j] = min(dp[j], dp[j - coin[i]] + 1);
		}
	}

	if (dp[K] == 100001) printf("-1");
	else printf("%d", dp[K]);

	return 0;
}
感じた点:点火式を探すことが大切らしい.
ArrayList vs Vector
[PG]JOYSTIC