[틀림] 백준 2294 동전2 c++ // dp 동전논리 정리, 규칙성발견 dp테이블 형식, 나누기보다는 덧셈

https://www.acmicpc.net/problem/2294

2294번: 동전 2

0. 규칙성발견 dp 테이블 형식

dp : target

후보들..

ex) dp : 0 1 2 3 4 5 ... 15 (target)

1

5

7(동전들)

dp[i][j] : i원 추가시 j원을 만드는 최소 동전갯수

i원들을 추가해나가면서 table을 완성시킨다 => 규칙성발견

 

 

1. 동전논리 정리 (j-coin)의 이유

5원일때)

dp[12]=d[7]+1

dp[7]의 경우에서 뒤에 5원만(1개) 더하면된다!

dp[7] : 1+1+1+1+1+1+1, 1+1+5,

dp[12] : 1+1+5+5

따라서, dp[12]=dp[12-5]+1 식이 나온다.

dp[12]=min(이전의d[12], d[12-5]+1)

 

2. 의사코드 추가(24.4.15.)

1. d[i][j] = min(위에값, 내코인한개만추가)

여기서 d[i-1][j]은 기존의 d[j]와 같다. -> 1차원으로 바꿔버릴수 있다.

d[i][j-coin] 도 d[j-coin]과 같다.

 

3. 전체코드

#include <bits/stdc++.h>
using namespace std;

int n, k,coin;
int dp[10000 + 4]; //dp[i] : i원을 만들때 사용하는 최소 동전의수

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;

	fill(dp, dp + 10000 + 4, 10004); //최소값구해야함 -> 최대값으로 초기화

	dp[0] = 0; // 초기값(0원을 만들때 최소사용 동전수는 0개)
	for (int i = 1; i <= n; ++i) { //동전만큼 회차
		cin >> coin;
		for (int j = coin; j <= k; ++j) {
			dp[j] = min(dp[j], dp[j - coin] + 1);
		}
	}
	if (dp[k] == 10004) cout << -1;
	else cout << dp[k];

	return 0;
}

 

* 2회독

• 1차시도
  • dp에 나누어떨어지는값으로 갱신해야되나?
  • 점점 복잡해짐..

• 2차시도
  • 나누어떨어지는지 검사하는대신 덧셈을 이용
  • dp[j] = min(dp[j], dp[j-tmp]) // min(위값 vs 내동전 1개만 추가)