글 읽기 - 캐시를 어떻게 구성하냐에 따라서 답이 다릅니다.

bono4023 3년 전 0

아래코드와 같이 cache를

int cache[flag][idx][cnt]로 선언하면 AC가 나옵니다.

하지만 cache를

int cache[idx][cnt][flag]로 구성하고 제출할때는 WA가 나오는데 이유를 알수있을까요?

#include<iostream>
#include<cstring>

using namespace std;

const int MOD = 1000000003;

int N, K, cache[2][1001][1001];

int sol(int idx, int cnt, bool flag) {
	if (cnt == K) return 1;

	int &ret = cache[flag][idx][cnt];
	if (ret != -1)return ret;

	ret = 0;
	for (int i = idx; i < N; i++) {
        //첫번째 색이 선택된 상태에서는 마지막 색이 선택되면 안된다.
		if (flag && i == N - 1)break;
		
        //첫번째 색이 선택되면 flag == true
		if (cnt == 0 && i == 0)flag = true;
		else if (cnt == 0 && i > 0)flag = false;
		
		ret += sol(i + 2, cnt + 1, flag);
		ret %= MOD;
	}
	return ret;
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> K;

	memset(cache, -1, sizeof(cache));
	cout << sol(0, 0, false);

	return 0;
}

3587jjh 3년 전 1

25째줄에서 i가 999이면 그 다음 호출에서 idx가 1001이 되고 배열 인덱스 범위를 벗어납니다.

벗어난 인덱스를 참조했을 때 무슨 값이 나올지는 undefined behavior이기 때문에 알 수 없고

맞은 코드도 따라서 우연히 맞았다고 봐야합니다.

bono4023 3년 전 0

크기를 늘리니 해결할 수 있었습니다 감사합니다 !

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

문제

문제

출처

ICPC

캐시를 어떻게 구성하냐에 따라서 답이 다릅니다.

bono4023 3년 전 0

3587jjh 3년 전 1

bono4023 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말