글 읽기 - 런타임 에러(Out of Bound)가 나옵니다.

ldhun041203 2년 전 0

문제 조건에서 주어진 수들이 100이하라는 것을 알려주었기 때문에,

그 합도 언제나 -10000 에서 10000사이에 있을거라 생각하였습니다.

Out of Bound 이면 범위가 문제일 텐데, N+1에 맞추어 102, 합의 범위도 고려하여 20001로 cache를 선언하였는데 이유가 무었인가요?

찾아주시면 정망 감사하겠습니다.........ㅠㅠ

#include <iostream>

#include <algorithm>
#include <string>
#include <cstring>
#include <memory>
#include <cmath>

//data structure
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <utility>
#include <set>
#include <list>
#include <tuple>

#define INF 987654321
#define MAX
#define X first
#define Y second

using namespace std;

typedef pair <int, int> pii;
typedef long long ll;

//--------struct,class-area


//---------variable-area

int N, T;
int A[102];
int cache[102][20001];

//---------function-area

int DP(int cur, int val) {
    if (cur == N+1 && val == T)
        return true;

    int& ret = cache[cur][val+10000];
    if (ret != -1) return ret;

    ret = 0;
    ret = ret | DP(cur+1, val + A[cur]);
    ret = ret | DP(cur+1, val - A[cur]);
    return ret;
}



//---------end

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

//----------start

    cin >> N >> T;
    memset(cache, -1, sizeof(cache));
    cache[N+1][T+10000]=1;
    for (int i = 1; i <= N; i++) cin >> A[i];
    DP(3,A[1]-A[2]);

    vector <int> ans;
    ans.push_back(1); ans.push_back(-1);
    int now = A[1] - A[2];
    for (int i = 3; i <= N; i++) {
        if (cache[i+1][now + A[i] + 10000] == 1) {
            ans.push_back(1); now += A[i]; continue;
        }
        if (cache[i+1][now - A[i] + 10000] == 1) {
            ans.push_back(-1); now -= A[i]; continue;
        }
    }

    int idx = 1;
    int ret[101];
    for (int i = 1; i < N; i++) {
        if (ans[i] != ans[i-1])
            idx = i;
        ret[i] = idx;
    }

    for (int i = N-1; i > 0; i--)
        cout << ret[i] << endl;

//-----------end

    return 0;
}

kdh6429 2년 전 0

수열의 길이가 100이라는 전제는 있는데, A[] 의 값이 100 이하의 정수라는 내용은 안보이네요.

합이 10000 미만이라고 생각하신 이유가 궁금합니다.

ldhun041203 2년 전 0

문제의 입력 설명에 A[i]가 100과 같거나 작은 자연수라고 나와있는 것 같습니다.

kdh6429 2년 전 0

제가 잘못봤네요 ^^;

DP함수가 재귀호출을 멈추는 조건이 부족한 것 같습니다.

val 이 T가 아니더라도 Cur == N+1 인 경우에는 false 를 리턴하면서 종료하게 했더니 통과되네요~~

ldhun041203 2년 전 0

감사합니다!

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

문제

문제

출처

ICPC

런타임 에러(Out of Bound)가 나옵니다.

ldhun041203 2년 전 0

kdh6429 2년 전 0

ldhun041203 2년 전 0

kdh6429 2년 전 0

ldhun041203 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말