티스토리 뷰

알고리즘/BOJ

백준 2293번 - 동전1

셩님 2017. 7. 15. 15:38

백준 2293 - 동전1

문제

  • n가지 종류의 동전이 있다.

  • 각각의 동전이 나타내는 가치는 다르다.

  • 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다.

  • 그 경우의 수를 구하시오. (각각의 동전은 몇 개라도 사용할 수 있다.)

입력

  • 첫째줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000)

  • 다음 n개의 줄에는 각각의 동전의 가치가 주어진다.

출력

  • 첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.

예제 입력

3 10
1
2
5

예제 출력

10

접근

  • Dynamic Programming으로 접근한다.

  • 첫 번째 동전만 사용하여 각 k값 마다 가능한 경우의 수를 찾는다.

  • 첫 번째~두 번째 동전만 사용하였을 때, 각k 값 마다 가능한 경우의 수를 찾는다.이 때, 첫 번째 동전만 사용해서 구했던 경우의 수를 활용한다.

  • 첫 번째~n 번째 동전을 사용하였을 때까지 반복한다.

점화식

  •  : i번째 코인의 가치

  •  : i번째 코인까지 사용하여 k를 만들 수 있는 경우의 수

풀이

1) 첫 번째 동전만 사용한 경우@

C(i) = [1, 2, 5]
D(i, k) =
      k   0   1   2   3   4   5   6   7   8   9   10
c(0)   [0] 1   0   0   0   0   0   0   0   0   0   0
c(1)   [1] 1   1   1   1   1   1   1   1   1   1   1

2) 두 번째 동전까지 사용한 경우

D(i, k) =
      k   0   1   2   3   4   5   6   7   8   9   10
c(0)   [0] 1   0   0   0   0   0   0   0   0   0   0
c(1)   [1] 1   1   1   1   1   1   1   1   1   1   1
c(2)   [2] 1   1   2   2   3   3   4   4   5   5   6

3) 세 번째 동전까지 사용한 경우

D(i, k) =
      k   0   1   2   3   4   5   6   7   8   9   10
c(0)   [0] 1   0   0   0   0   0   0   0   0   0   0
c(1)   [1] 1   1   1   1   1   1   1   1   1   1   1
c(2)   [2] 1   1   2   2   3   3   4   4   5   5   6
c(3)   [5] 1   1   2   2   3   4   5   6   7   8   10

C++ Code - 1

#include <cstdio>

int main() {
   int n, k;
   int c[101];
   int d[101][10001] = {0, };

   scanf("%d %d", &n, &k);
   for (int i = 1; i <= n; i++) {
       scanf("%d", &c[i]);
  }
   
   for (int i = 1; i <= n; i++) {
       d[i][0] = 1;
  }

   for (int i = 1; i <= n; i++) {
       for (int j = 1; j <= k; j++) {
           if (j >= c[i]) {
               d[i][j] = d[i - 1][j] + d[i][j - c[i]];
          }
           else {
               d[i][j] = d[i - 1][j];
          }
      }
  }

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

   return 0;
}
  • 위의 점화식을 그대로 구현한 코드

  • 메모리를 많이 잡아 먹는다.4 x (101 + 101 x 10001) = 4,080,408 Bytes = 약 3.9 MB + @

  • 현재 이 코드를 BOJ에 제출하면 메모리 초과가 난다.

C++ Code 2

#include <cstdio>

int main() {
   int n, k;
   int coins[101];
   int d[10001] = {0};

   scanf("%d %d", &n, &k);
   for (int i = 1; i <= n; i++) {
       scanf("%d", &coins[i]);
  }
   
   d[0] = 1;

   for (int i = 1; i <= n; i++) {
       for (int j = 1; j <= k; j++) {
           if (j >= coins[i]) {
               d[j] += d[j-coins[i]];
          }
      }
  }

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

   return 0;
}
  • i-1번째 경우의 수 배열에 i 번째 경우의 수 배열을 덮어 씌운다.

  • 메모리 절약형


'알고리즘 > BOJ' 카테고리의 다른 글

백준 2580번 - 스도쿠  (0) 2017.07.19
백준 9663번 - N Queen  (0) 2017.07.19
백준 10844번 - 쉬운 계단 수  (2) 2017.07.15
백준 2156번 - 포도주 시식  (2) 2017.07.15
백준 1912번 - 연속합  (0) 2017.07.15
백준 2293번 - 동전1  (5) 2017.07.15
댓글
  • 프로필사진 이재호 점화식 부등호 방향 반대에다가 두번째 C(i) <= k 일 때 D(i - 1, k)도 다시 더해줘야하지 않나요? 2018.08.10 11:57
  • 프로필사진 셩님 감사합니다! 수정했어요~! 2018.08.11 21:08 신고
  • 프로필사진 질문이 10 10000
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    하면 -로 큰값이 나오는데 왜그런가요??
    2019.07.26 23:53
  • 프로필사진 지나가는 행인A 배열 d 를 long 이나 long long 으로 하시면 정상적으로 나올 겁니다 int 의 범위를 초과해서 그런 것 같네요,,, 수정 부탁드립니다! 2019.11.04 22:53
  • 프로필사진 ㅇㅇ 출력 조건에 경우의 수가 2^31보다 작다고 나와있어서 그렇게 할 필욘 없어요. 2020.06.05 10:33
댓글쓰기 폼