[C/C++ 백준 2293번] 동전 1 (Silver 1)

www.acmicpc.net/problem/2293

2293번: 동전 1

굉장히 유명한 문제라 풀이도 대부분 알 거라 생각한다. 이차원 dp배열을 만든 이후, 해당 코인을 사용할 때와 사용하지 않을 때로 나누어 해당 dp를 구하면 된다 (dp[i][j] = dp[i-1][j] + dp[i][j-coin[i]).

 

물론 이 문제를 그렇게 풀면 메모리 초과가 나므로, 과감하게 i항을 모두 지워주자.

 

#include <cstdio>
int dp[10001];
int main(void){
	int n, k, coin[101];
	scanf("%d %d", &n, &k);
	for(int i=0; i<n; i++){
		scanf("%d", &coin[i]);
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<=k; j++){
			if(j==0)
				dp[j] = 1;
			if(i==0 && j%coin[i]==0)
				dp[j] = 1;
			else{
				if(j>=coin[i])
					dp[j] = dp[j-coin[i]] + dp[j];
				else
					dp[j] = dp[j];
			}
			//printf("%d ",dp[j]);
		}
		//printf("\n");
	}
	printf("%d", dp[k]);
}