글 읽기 - DP 2차원으로 풀 때 질문입니다.

cesta123 5년 전 0

1차원으로는 동전 a[1]~a[j]가 있을 때, d[i] : i원을 만드는 최소 동전 개수로 해서 d[i] = min(d[i-a[j]) + 1로 해서 잘 풀어보았습니다. 그리고

2차원으로 풀 때 d[i][j] : a[1] ~ a[i] 동전까지 사용했을 때 j원을 만드는 최소 개수로 해서 풀려고 해봤습니다. d[i][j] = min(d[i-1][j-a[i]]) + 1로 했는데요

그런데 제가 식을 잘못 정의한건지 푸는 방법에 좀 문제가 있는 거 같아서 질문드립니다.

코드 결과 증상을 봐보니까 예를들면 15원을 만들 때 5원 3개쓰는 것이 최소인데 동전을 한번씩만 사용해서 개수 구하는? 그런 거로 보이는데

솔직히 제가 어떤식으로 바꿔야할 지 잘 모르겠어서 질문드립니다.. 고수님들 부탁드릴게요.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int d[101][10001];

int main(){
	int n, k;
	cin >> n >> k;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}
	memset(d, -1, sizeof(d));

	for (int i = 0; i <= n; i++)
		d[i][0] = 0;

	for (int j = 0; j <= k; j++){
		for (int i = 1; i <= n; i++){
			if (j - a[i] >= 0 && d[i - 1][j - a[i]] != -1){
				if (d[i][j] == -1 || d[i][j] > d[i - 1][j - a[i]] + 1){
					d[i][j] = d[i - 1][j - a[i]] + 1;
				}
			}
		}
	}
	/*for (int i = 1; i <= n; i++){
		for (int j = 1; j <= k; j++){
			cout << d[i][j] << ' ';
		}
		cout << '\n';
	}*/
	cout << d[n][k] << '\n';
	return 0;
}

h0ngjun7 5년 전 1

정의를 "d[i][j] : a[1] ~ a[i] 동전까지 사용했을 때 j원을 만드는 최소 개수"로 하셨기 때문에

d[i][j] = min( d[i-1][j], min(d[i][j-a[i]])+1 )이 됩니다.

작성하신 d[i-1][j-a[i]]+1는 a[1] ~ a[i-1]동전까지 사용한 최적해에다가 i번째 동전을 한 번만 쓰는 것이기 때문입니다.

cesta123 5년 전 0

답변 너무 감사합니다!!

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

문제

문제

출처

ICPC

DP 2차원으로 풀 때 질문입니다.

cesta123 5년 전 0

h0ngjun7 5년 전 1

cesta123 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말