CSES PS - Coin combinations (DP)

https://cses.fi/problemset/task/1636

점화식 만들기가 쉽지 않다.

https://www.youtube.com/watch?v=DJ4a7cmjZY0

영상설명..

 

<문제설명>

서로 다른 동전의 가치가 최대 100개 주어질때, 이 동전을 이용해서 정확하게 x원을 사용하는 경우의 수를 구해라.

(단, 예를들어, 2 2 2 5와 5 2 2 2 는 같은 경우로 친다)

 

<풀이>

위에서 든 예시와 같은 경우가 생기지 않도록 동전의 순서를 강제해야 한다.

 

f(k, i) = k원을 만드는데 0~i번째 동전을 순서대로 사용해서 만드는 경우의 수.

        = f(k-a[i], i) + f(k, i-1) ... ->마지막으로 i번째 동전을 사용하거나, 사용하지 않거나

 

예제로 dp 테이블을 채워보면 다음과 같다.

 

수정 귀찮 [2,3]라인 x=4일때 1이다.

테이블이 채워지는 순서를 이용하면 1차원 dp로도 풀 수 있다. 

 

 

<코드>

int n, x, a[101], d[101][MAX]{ 0 };
int main() {
	FAST;
	cin >> n >> x;
	for (int i = 1; i <= n; i++) cin >> a[i];

	d[0][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= x; j++) {
			if (a[i] <= j) d[i][j] = (d[i - 1][j] + d[i][j - a[i]]) % MOD;
			else d[i][j] = d[i - 1][j];
		}

	cout << d[n][x] << '\n';
}

 

최적화된 코드

 {
  for (int i = 0; i < n; i++) cin >> a[i];
  d[0] = 1;
  for (int c : a)
    for (int i = 1; i <= x; i++)
      if (c <= i) d[i] = (d[i] + d[i - c]) % 1000000007;
  cout << d[x] << "\n";
}

 

 

<생각>

순서를 강제해야 한다는 것을 잡지 못해서 이해하는데 1시간은 걸린 것 같다.

 

유튜브 보니 완전 기본문제던데 (조회수4만) ps 시작한지 벌써 3분기정도 되는데 처음본다..

 

영어권 친구들이 ps를 잘할 수 밖에 없는 것 같다.