문제
풀이
1번째 동전으로만 1~M까지 만들 수 있는 경우의 수들을 체크, 1~2번째 두개의 동전으로만 1~M까지 만들 수 있는 경우의 수들을 체크해 나가며, 1~N번째의 동전으로 M을 만들 수 있는 경우의 수를 확인하는 문제이다. i번째까지 동전으로 M을 만들 수 있는 경우의 수는 i-1번째까지 동전으로 M을 만들 수 있는 경우의 수 + i번째까지 동전으로 M-arr[i]를 만들 수 있는 경우의 수(여기에 arr[i]를 추가하면 되기 때문)를 더하면 된다. 아래의 코드는 기존에 이중벡터로 계속해서 지나왔던 값들을 저장하는 경우는 메모리초과가 일어난다. 하지만, 그 직전 i값만 알고 있으면 되기에, 소스 코드에 있는 식으로 이중벡터 사용 필요없이 덧셈해나가며 정답을 도출해냈다.
메모리 초과 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>
using namespace std;
int main(){
int N, M;
scanf("%d %d", &N, &M);
vector<int> arr(N);
for(int i = 1; i<=N; i++){
scanf("%d", &arr[i]);
}
vector<vector<int>> dp(M, vector<int>(M));
for(int i = 1; i<=N; i++){
dp[i][0] = 1;
}
for(int i = 1; i<=N; i++){
for(int j = 1; j<=M; j++){
if(j >= arr[i]) dp[i][j] = dp[i-1][j] + dp[i][j-arr[i]];
else{
dp[i][j] = dp[i-1][j];
}
}
}
printf("%d\n", dp[N][M]);
}
/*
arr[1] = 1;
arr[2] = 2;
arr[3] = 5;
M = 10;
*/
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <vector>
using namespace std;
int main(){
int N, M;
scanf("%d %d", &N, &M);
vector<int> arr(N+1);
for(int i = 1; i<=N; i++){
scanf("%d", &arr[i]);
}
vector<int> dp(M+1);
dp[0] = 1;
for(int i = 1; i<=N; i++){
for(int j = 1; j<=M; j++){
if(j >= arr[i]) dp[j] += dp[j-arr[i]];
}
}
printf("%d\n", dp[M]);
}
/*
arr[1] = 1;
arr[2] = 2;
arr[3] = 5;
M = 10;
*/
