백준 BOJ 2293 - 동전 1

​https://www.acmicpc.net/problem/2293

2293번: 동전 1

 

풀어보았다.

dp용 배열 arr은 걍 널찍널찍하게 잡았고, arr[i]는 i원을 만들 수 있는 경우의 수이다.

#include <stdio.h>

int n,input[101],k;
int arr[100001] = {0};

int main(){
	scanf("%d %d", &n, &k);
	for(int i=0; i<n; i++){
		scanf("%d", &input[i]);
	}
	arr[0] = 1;
	for(int i=0; i<n; i++){
		for(int j=0; j<k; j++){
			arr[j+input[i]] += arr[j];
		}
	}
	printf("%d", arr[k]);
	return 0;
}