동전2 | 백준 2294번

#include <cstdio>

int main(void) {
 int n, k, num;
 int N[100], K[10001]={0};
 
 scanf("%d%d", &n, &k);
 
 for(int j=0; j<n; j++)
 {
  scanf("%d", &N[j]);
  if(N[j] <= 10000) K[N[j]] = 1; //받은 값에 표시함
 }
 
 for(int i=1; i<= k; i++)
 {
  if(K[i]==1) continue; //K[i]가 주어진 동전 값이라는 것
  
  num= 10001;
  
  for(int j=0; j<n; j++)
  {
   if(i-N[j] <= 0) continue; // 동전 값만큼 뺐을 때 0보다 작거나 같으면 무시
   if(K[i-N[j]] <= 0) continue; // 동전을 뺀 값이 0보다 작다는 것은 뺀 값이 구해지지 않는 다는 것. 무시
   
   if(K[i-N[j]] + 1 < num) num = K[i-N[j]] + 1; // 동전 값을 뺄 수 있고, 그 값에서 현재 동전 하나를 더한게 더 작으면 저장
  }
  if(num==10001) num = -1; // 모든 동전을 다해도 안된다는 것
  K[i] = num;
 }

 printf("%d\n", K[k]);

 return 0;
}

주석으로 설명을 대체하고자 한다.

상세 설명을 하면, 이 문제는 sorting을 한 후 풀면 더 쉽지만, 시간 효율을 고려해 다음과 같이 풀었다.

처음 scanf를 할 때, 가진 동전을 표시한다. 예를 들면 위의 코드에서 15를 입력했다면 K[15]=1 로 15 동전이 있는 것을 표시.

아래 반복문에서는 표시한 동전이 있는 경우 무시한다. 왜냐면 걘 어짜피 하나면 되거든.

그 안의 반복문은 동전 개수만큼 반복하는 것이고,