gj3034   3년 전

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 3067. Coins
#include <iostream>
#include <vector>
 
using namespace std;
 
int t, n, m;
vector<int> vec;
 
int dp[10010][21];
 
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
 
    cin >> t;
 
    while (t--)
    {
        cin >> n;
        fill(&dp[0][0], &dp[0][0] + 10010 * 21, 0);
        vec.clear();
 
        int a;
        for (int i = 0; i < n; i++)
        {
            cin >> a;
            vec.push_back(a);
        }
 
        cin >> m;
 
        // cur == m 경우
        for (int i = 0; i < n; i++)
        {
            dp[m][i] = 1;
        }
 
        for (int i = m; i >= 0; i--)
        {
            for (int j = 0; j < n; j++)
            {
                for (int k = j; k < n; k++)
                {
                    dp[i][j] += dp[i + vec[k]][k];
                }
            }
        }
 
        cout << dp[0][0] << '\n';
    }
 
    return 0;
}
cs

위는 제가 풀이한 코드입니다. (미숙하지만..)
주어진 N가지 동전으로 만들어야 할 금액 M(1 ≤ M ≤ 10000) 에 맞추어 dp 배열을 선언하고 코드를 작성했으나.

위의 코드에는 "런타임 에러(OutOfBounds)" 가 발생합니다.

코드의 M 제한을 50000 정도로 올렸을 때는 무리 없이 통과하구요.

문제의 데이터에 M이 10000을 초과하는 데이터가 있는 것 같으니 확인 부탁드립니다.

bumsoo0515   3년 전

vec[k]의 최댓값이 10000이기에 i가 10000에 가까우면 dp[i + vec[k]][k]가 범위를 벗어날 것 같습니다.

assert로 확인한 결과 범위를 벗어나는 입력은 없습니다.

gj3034   3년 전

아 그렇군요 제가 생각이 짧았네요.. 허허...

상세한 설명 감사드립니다..!

댓글을 작성하려면 로그인해야 합니다.