[2293] 동전1

• 입력: 동전 개수 N, 만드려는 수 K, 동전 N개의 가치
• 출력: K를 만들 수 있는 경우의 수
• 알고리즘: 동적 계획법
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> #include <algorithm> using namespace std; vector<int> dp(10001, 0); vector<int> coins(100); int main() { //freopen("input.txt", "r", stdin); int N, K; scanf("%d%d", &N, &K); for (int i = 0; i < N; i++) scanf("%d", &coins[i]); sort(coins.begin(), coins.begin() + N); for (int i = 0; i < N; i++) { dp[coins[i]]++; for (int j = 1; j + coins[i] <= K; j++) { dp[coins[i] + j] += dp[j]; } } printf("%d\n", dp[K]); return 0; }

bottom-up으로 푸는 방식으로 가장 작은 동전부터 dp를 저장해나가는 식이다. 

• 문제 출처: https://www.acmicpc.net/problem/2293