뚝딱뚝딱

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

💡 동전 1

✅ 문제 풀이

• 배낭 문제와 접근 방식이 동일하다.
• dp를 이용해 경우의 수를 구해나간다.
• dp[i]=j 는 "n가지 종류의 동전을 이용해서 합이 i원이 되도록 하는 경우의 수가 j개" 라는 뜻이다.
• dp[0]=1이다. 합이 0원이 되는 경우의 수는 아무것도 합하지 않는 경우 1개가 존재하기 때문이다. 따라서 이는 초기값이 된다.
• 만약 동전 종류 중 1원짜리가 있다고 하자. 1원을 가지고 1원을 만드는 경우의 수는 다음과 같다.
  dp[1]=dp[1]+dp[0]
  1원이 되려면, 0원에다가 1원을 더해주면 되니까 0원이 되는 경우의 수를 합해주면 된다. 따라서 1이다.
• 만약 동전 종류 중 3원짜리가 있다고 하자. 3원을 가지고 5원을 만드는 경우의 수는 다음과 같다.
  dp[5]=dp[5]+dp[2]
  5원이 되려면, 2원에다가 3원을 더해주면 되니까 2원이 되는 경우의 수를 합해주면 된다. 
• 즉 dp[i]를 구하려면 i에서 동전 가치 "value[j]"를 빼준 값이 되는 경우에다가 그냥 value[j]를 더하면 i원이 되는 거니까. dp[i-value[j]]를 구하는 것과 동일하다. 즉 i-value[j]원이 되는 경우의 수를 구하는 것과 같다.
• 주의할 점은 어떤 value[j]를 가지고서 i원이 되도록 할 때, i는 value[j]보다 커야 한다는 것이다.
  예를 들어, 3원을 더함으로써 4원을 만들어낼 수 있지만, 3원을 더함으로써 2원을 만들어낼 수는 없다. 이미 3이라는 가치가 2보다 크기때문에, 3원을 더하려면 항상 3원 이상의 큰 가치만을 만들어 낼 수 있다.
• 따라서 다음과 같은 점화식을 따른다.
  dp[i]+=dp[i-value[j]]
  (이때, i>=value[j])
• 위를 모든 동전의 종류에 대해서 반복해주면 된다.
• 최종 답은 dp[k]이다. k원을 만드는 경우의 수 이기 때문이다.   

✏ 코드 전문

#include<iostream>
#include<vector>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;
	cin >> n >> k;

	vector<int> value(n);
	for (int i = 0; i < n; i++) {
		cin >> value[i];
	}

	vector<long long> dp(k + 1,0); //출력 범위가 2^31 까지 임에 주의하여 long long으로 선언

	dp[0] = 1;//0원을 만드는 데 필요한 경우의 수 1

	for (int i = 0; i < n; i++) {
		for (int j = value[i]; j <= k; j++) {
			dp[j] += dp[j - value[i]];//j원을 만드는데, value[i]원을 사용하려면 j에서 value[i]를 뺀 값이 필요하고, 이것의 경우의 수를 더해주면 됨.
		}
	}

	cout << dp[k];

	return 0;
}