[Week of DP] BOJ 2294 #1

문제 : www.acmicpc.net/problem/2294

 

DP문제에서 가장 흔하게 보이는 유형이다.

 

일단 가장 큰 문제로 파악되는건

n의 갯수에 따라서 시간 복잡도가 늘어날 것 같아 보인다.

(시간 초과의 가능성 높음)

 

처음 접근은 n을 가지고 조합을 구해보면 되지 않을까..? 였다.

그런데 n = 3이고 k가 [1,2,3]인 경우에는

3C1 = [1], [2], [3]

3C2 = [1, 2], [1, 3], [2, 3]

3C3 = [1, 2, 3]

이렇게 조합은 나오는데.. 문제는 각각의 동전들의 갯수가 몇 개인지 찾는건 또 다른 문제였다.

 

여기서 막혔다.

 

책이나 인터넷을 검색해서 어떤 방법을 쓰면 좋을지 알아보자.