반응형 DP1 [DP] Dynamic Programming (동적 계획법) 정복하기 문제: 자판기 조합 수 세기자판기에는 여러 상품이 있고, 각 상품의 가격이 주어진다. 목표 금액 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 방식으로 한 번만 고를 수 있다.같은 값이 여러 번 등장할 수.. 2025. 10. 31. 이전 1 다음