2294 어려운 동전 2

www.acmicpc.net/problem/2294

 

dp배열은 합이 j일 때의 최소 동전 개수를 나타낸다

현재 금액만 사용했을 때 최소 몇 개의 동전이 필요한가 하나씩 보며 전체 dp배열을 업데이트하는 식이다

1원 쓸 때는 1~15원까지 각 개수만큼 사용해서 1,2,3..15까지가 배열에 들어간다

다음 5원 쓸 때는 1~4원까지는 1원을 쓴 그대로 두고, 5원은 5원 1개로 만들 수 있으니까 1이 되고,
6,7,8,9까지는 5+x개의 1원을 쓰니까 각각 2,3,4,5개를 사용해서 만들 수 있다

 

이 때 이전에 1원 기준으로 계산했던 값에서+5원을 하면 (5원 1개+1원 x개)로 만든 값이 나오니까
j-a[i](1원 x로 만든 값)+1(5원 1개 더한 값)이 식이다. j-a[i]+1

이 값을 현재까지의 최소값과 비교해서 더 작은 값을 구하면 된다

min(원래 만들 수 있는 동전조합의 경우의 수, 가치가 coin[i]인 동전 1개 더함) 인 것이다

 

다음 10은 5원 2개로 되니까 2가 되고, 11~14는 5원 2개+x개니까 아까와 같이 갱신한다

 

그렇게 a[i]배열인 1,5,12 세 개에 대해서 1~k까지의 값들을 만들 수 있는 최소 동전 수를 전부 구한다

 

배열 값이 갱신되는 모습은 m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=220794872664&proxyReferer=http:%2F%2F203.229.225.135%2F 여기서 자세히 볼 수 있다

 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[10001]; //합이 i일 때의 최소 동전 개수
int a[10001];
int main() {
	int n, k;
	cin >> n >> k;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= k; i++) dp[i] = 99999; //최대 동전 개수
	dp[0] = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = a[i]; j <= k; j++) {
			dp[j] = min(dp[j], dp[j - a[i]] + 1); //현재까지의 최소값vs이전에 만든 최소값+현재 값을 더함
		}
	}
	if (dp[k] != 99999) cout << dp[k];
	else cout << -1;
}

 

 

 

1669 제곱수의 합도 비슷한 문제

www.acmicpc.net/problem/1699

 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[100001]; //합이 i일 때의 최소 제곱수의 합
int a[100001];
int main() {
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) {
		dp[i] = i; //합 구하는 dp특징: 자기 자신을 최소 합으로 가진다
		for (int j = 1; j * j <= i; j++) {
			dp[i] = min(dp[i], dp[i - j * j] + 1);
		}
	}
	//for (int j = 0; j <= n; j++) {
	//	cout << dp[j] << " ";
	//}

	cout << dp[n];
}

 

합을 구하는 dp는 다들 저렇게 자기 자신을 최소 값으로 넣는 과정이 있다

 

여기서도 모든 dp배열의 값을 구할 건데, 역시 뒤에서부터 구하고 이전의 값+1인 식을 사용한다

 

전체 항이 n이고 마지막 항이 i면 i를 제외한 부분은 n-i*i

여기선 합이 i이고 마지막 항이 j일 때를 하나씩 봐 주니까 i, j로 사용