글 읽기 - 배열 음수 인덱스 접근

xgboost 5년 전 0

아래 코드는 AC를 받은 코드인데 a배열과 dp배열에 범위를 MAX_SIZE + 2가 아닌
MAX_SIZE + 홀수로 하면 틀린 답이 나옵니다.
j == 0 일때 j 가 음수에 접근하는 순간이 있는데 그것과 연관이 있는 건가요?
궁금합니다..

#include <iostream>
using namespace std;
const int MAX_SIZE = 1000;
inline int max(int a, int b) {
	return (a > b) ? a : b;
}
int a[MAX_SIZE + 2], dp[2][MAX_SIZE + 2][32], T, W;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> T >> W;
	for (int i = 1; i <= T; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= T; i++) {
		for (int j = 0; j <= W; j++) {
			if (a[i] == 1) {
				dp[0][i][j] = max(dp[0][i][j], dp[0][i - 1][j] + 1);
				dp[0][i][j] = max(dp[0][i][j], dp[1][i - 1][j - 1] + 1);

				dp[1][i][j] = max(dp[1][i][j], dp[1][i - 1][j]);
				dp[1][i][j] = max(dp[1][i][j], dp[0][i - 1][j - 1]);
			}
			else {
				dp[0][i][j] = max(dp[0][i][j], dp[0][i - 1][j]);
				dp[0][i][j] = max(dp[0][i][j], dp[1][i - 1][j - 1]);

				dp[1][i][j] = max(dp[1][i][j], dp[1][i - 1][j] + 1);
				dp[1][i][j] = max(dp[1][i][j], dp[0][i - 1][j - 1] + 1);
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= W; i++) {
		ans = max(ans, max(dp[0][T][i], dp[1][T][i]));
	}
	cout << ans << '\n';
	return 0;
}

k5nen 5년 전 1

dp[0][0][-1]처럼 메모리상에 할당된 변수, 배열 공간을 벗어난 위치가 원래 사용중이었을지는 정의되어 있지 않습니다.

그 장소가 할당되지 않은 메모리 공간이었다면 큰 문제가 없을 수 있지만, 다른 변수를 저장하는 위치였다면 고치기 어려운 아주 악랄한 버그로 이어질 수도 있습니다.

따라서 이런 코드가 가져올 수 있는 부작용을 잘 이해하기 전에는 사용하지 말 것을 강하게 권장드립니다.

xgboost 5년 전 0

감사합니다 그러면 음수 인덱스에 접근하는 이유로 저런 버그가 생겼다고 볼수 있는건가요?

k5nen 5년 전 1

네. MAX_SIZE + 홀수 크기로 배열을 선언해도 19, 22, 26, 29행에 j가 0보다 큰지 확인하는 코드를 넣으면 정답을 받습니다.

if(j) dp[0][i][j] = max(dp[0][i][j], dp[1][i - 1][j - 1] + 1);

xgboost 5년 전 0

감사합니다

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

문제

문제

출처

ICPC

배열 음수 인덱스 접근

xgboost 5년 전 0

k5nen 5년 전 1

xgboost 5년 전 0

k5nen 5년 전 1

xgboost 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말