2294번 문제 메모

참고: 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

 

동전 n가지를 무한히 쓸 수 있다? == dp를 왼쪽부터 누적

동전 n가지를 1개만 쓸 수 있다? == dp를 오른쪽부터 누적.

 

0 1 2 3 4 5 6 7 8

1원으로 얘네들을 만든다.

1 2 3 4 5 6 7 8개가 필요.

2원으로 만든다.

테이블로 표현하자.

 

 

dp	0	1	2	3	4	5	6	7	8
1원	0	1	2	3	4	5	6	7	8
2원	0	1	1	2	...

빨간 글씨부터 갱신이 되는 부분이다. 즉, 점화식이 min(dp[i], dp[i-2] + 1);이다.

 

 

번외) n가지를 1개만 쓸 수 있다면?

for (int i = 0; i < n; i++) {
  int tmp = Integer.parseInt(br.readLine());
  for (int j = k; j >= tmp; j--) {
    dp[j] = Math.min(dp[j], dp[j - tmp] + 1);
  }
}

 

1, 2, 5로 5원을 만든다고 하면 테이블이 다음처럼 이루어진다.

 

dp	0	1	2	3	4	5
1원	0	1	inf	inf	inf	inf
2원	0	1	1	2	inf	inf
5원	0	1	1	2	inf	1

 

흐름을 따라가면 모두 1개만 사용해서 k원을 만드는 것을 볼 수 있다. 근데 흐름을 따라가면 이렇게 나오는건 알겠는데, 왜 이렇게 되는건지는 아직 잘 모르겠다.