문제
정수 n
을 주어진 money
배열의 값들을 이용해 구성할 수 있는 경우의 수를 구하는 문제
풀이
처음에는 n
이 되는 경우의 수는 n-money[i]
를 모두 더한 값이라고 생각했다. 그래서 vector 하나에 값을 업데이트 하면서 답을 구했는데, 이렇게 하면 값이 중첩돼서 답이 나오지 않았다.
ex) 5를 1, 2, 5 로 구성하는 경우
4를 만드는 경우의 수 -> 1111, 112, 22
3을 만드는 경우의 수 -> 12, 111
0을 만드는 경우의 수 -> 1
3에서 5가 되는 경우 122, 4에서 5가 되는 경우 122 => 중첩
dynamic programming의 기본은 이차원 배열을 이용하는 것이라고 한다.
특정 숫자 n을 만드는 경우의 수는
money[i]
까지 수를 모두 사용해 만드는 경우 + money[i-1]
까지만 사용해 만드는 경우로 구성된다.
money[i-1]
까지 사용해서 n을 만드는 경우 ->dp[i-1][n]
money[i]
까지 사용해서 n을 만드는 경우 -> dp[i][j-money[i]]
처음열들을 잘 초기화하고 위의 아이디어를 사용해 문제를 해결하였다.
어려웠다.
#include <string>
#include <vector>
#include <vector>
using namespace std;
int solution(int n, vector<int> money) {
int answer = 0;
int dp[money.size()][n+1];
for(int i=0; i<money.size(); i++){
for(int j=0; j<=n; j++){
if(j==0){
dp[i][j] = 1;
}
else{
dp[i][j] = 0;
}
}
}
for(int i=0; i<money.size(); i++){
for(int j=0; j<=n; j++){
if(i==0&&j*money[i]<=n){
dp[i][j*money[i]] = 1;
}
else if(j>=money[i]){
dp[i][j] = dp[i-1][j] + dp[i][j-money[i]];
}
else{
dp[i][j] = dp[i-1][j];
}
}
}
answer = dp[money.size()-1][n];
return answer%1000000007;
}
2차원 배열을 사용하지 않고도 풀 수 있는 문제라고 한다.
참고 : https://ansohxxn.github.io/programmers/106/#-3-%EC%B0%A8-%ED%92%80%EC%9D%B4--dp