동전 1 C++ - 백준 2293

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

이 문제의 풀이는 dp table을 작성할 때 데이터를 조금 색다르게 저장하는
방식이어서 글을 쓴다.

보통 dp 문제를 풀때 하나에 dp table 값에 대해 이중 for문이나 여러가지
알고리즘을 수행하지만 이 문제는 하나의 값에 대해 dp table 전체에 대한 수행을 진행했다.

(단이님의 블로그를 참조했습니다.)

동전으로 만들 수 있는 경우의 수에 대해 차례 대로(입력이 오름차순이었어서 가능하다.) dp값을 메모이제이션 하면 모든 경우의 수가 탐색된다.(중복 없이)

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int dp[10001];
int coin[101];
int n;
int k;

int main(){
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	
	dp[0]=1;
	cin >> n >> k;
	for(int i=0;i<n;i++){
		cin >> coin[i];
	}
	
	for(int i=0;i<n;i++){
		for(int j=coin[i];j<=k;j++){
			dp[j]+=dp[j-coin[i]];
		}
	}
	
	cout << dp[k];
}

이미지 출처 : https://danidani-de.tistory.com/5