문제: 자판기 조합 수 세기
자판기에는 여러 상품이 있고, 각 상품의 가격이 주어진다. 목표 금액 N원이 주어질 때, 상품을 각 1번씩만 사용할 수 있다고 하면
(같은 가격이라도 서로 다른 상품이면 각기 1번씩 선택 가능)
가격 합이 정확히 N원이 되는 선택 방법의 가짓수를 구하라.
선택 순서는 고려하지 않는다(즉, {A,B}와 {B,A}는 같은 방법).
입력 형식
- 첫 줄에 정수 N (1 ≤ N ≤ 10,000)
- 둘째 줄에 정수 M (1 ≤ M ≤ 2,000): 상품 개수
- 셋째 줄에 길이 M의 정수 배열 prices: 각 상품 가격 (1 ≤ prices[i] ≤ N)
출력 형식
- 합이 정확히 N원이 되는 선택 방법의 가짓수를 정수로 출력한다.
설명
- 각 상품은 0/1 방식으로 한 번만 고를 수 있다.
- 같은 값이 여러 번 등장할 수 있으며, 그 경우 서로 다른 상품으로 구분되어 다른 선택으로 카운트된다.
- 조합의 순서는 무시한다.
예제1
10
5
8 1 1 3 6
출력 1
예제2
10
5
7 3 3 4 6
출력 2
정답
def solution(N, M, prices):
dp = [0] * (N + 1) // 0원부터 N원까지 모두 저장해야함
dp[0] = 1
for p in prices:
for s in range(N, p - 1, -1): // 역순으로 돌기
dp[s] += dp[s - p]
return dp[N]
가격을 하나씩 보면서 각 가격을 포함했을 때 만들 수 있는 금액 조합 수를 누적하는 방식
dp[s] = 금액 s원을 만드는 방법 수
왜 DP를 역순(for s in range(N, p-1, -1))으로 도는가?
각 상품을 딱 1번만 사용하기 위해서
반응형