글 읽기 - 쓰이지도 않는 전역으로 선언된 배열에 따라 채점이 달라집니다.

dltkdtn56 2년 전 0

선언만 하고 쓰이지도 않는 9번째 줄의 MAP 배열을 선언하면 맞았습니다. 를 받아 통과할 수 있고

MAP배열을 선언하지 않고 나머지는 모두 똑같은 코드를 사용하면 틀렸습니다.가 뜨며 통과되지 않습니다.

아무리 생각해도 잘 모르겠습니다. 무엇이 문제인지 알 수 있을까요??

// 맞았습니다. 를 받는 코드
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int h, w, n, Answer;
bool MAP[100][100]; // 이 코드로 인해 맞았습니다.를 받습니다.
bool Select[101];
bool Select2[101];
vector<pair<pair<int, int>, int>> V;
vector<pair<int, int>> Sticker;

void DFS(int Idx, int Cnt)
{
	if (Cnt == 2) {
		int x1 = Sticker[0].first;
		int y1 = Sticker[0].second;
		int x2 = Sticker[1].first;
		int y2 = Sticker[1].second;
		int point = (x1 * y1) + (x2 * y2);

		if (x1 + x2 <= h && y1 <= w && y2 <= w) Answer = max(Answer, point);
		if (y1 + y2 <= w && x1 <= h && x2 <= h) Answer = max(Answer, point);
		return;
	}

	for (int i = Idx; i < V.size(); i++) {
		if (Select[i] || Select2[V[i].second]) continue;
		Select[i] = true;
		Select2[V[i].second] = true;
		Sticker.push_back({ V[i].first.first, V[i].first.second });
		DFS(i + 1, Cnt + 1);
		Sticker.pop_back();
		Select[i] = false;
		Select2[V[i].second] = false;
	}
}

int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin >> h >> w >> n;
	for (int i = 0; i < n; i++)
	{
		int a, b; cin >> a >> b;

		if (a != b)
		{
			V.push_back(make_pair(make_pair(a, b), i));
			V.push_back(make_pair(make_pair(b, a), i));
		}
		else V.push_back(make_pair(make_pair(a, b), i));
	}
	DFS(0, 0);
	cout << Answer << '\n';
	return 0;
}



// 틀렸습니다. 를 받는 코드
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int h, w, n, Answer;
bool Select[101];
bool Select2[101];
vector<pair<pair<int, int>, int>> V;
vector<pair<int, int>> Sticker;

void DFS(int Idx, int Cnt)
{
	if (Cnt == 2) {
		int x1 = Sticker[0].first;
		int y1 = Sticker[0].second;
		int x2 = Sticker[1].first;
		int y2 = Sticker[1].second;
		int point = (x1 * y1) + (x2 * y2);

		if (x1 + x2 <= h && y1 <= w && y2 <= w) Answer = max(Answer, point);
		if (y1 + y2 <= w && x1 <= h && x2 <= h) Answer = max(Answer, point);
		return;
	}

	for (int i = Idx; i < V.size(); i++) {
		if (Select[i] || Select2[V[i].second]) continue;
		Select[i] = true;
		Select2[V[i].second] = true;
		Sticker.push_back({ V[i].first.first, V[i].first.second });
		DFS(i + 1, Cnt + 1);
		Sticker.pop_back();
		Select[i] = false;
		Select2[V[i].second] = false;
	}
}

int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin >> h >> w >> n;
	for (int i = 0; i < n; i++)
	{
		int a, b; cin >> a >> b;

		if (a != b)
		{
			V.push_back(make_pair(make_pair(a, b), i));
			V.push_back(make_pair(make_pair(b, a), i));
		}
		else V.push_back(make_pair(make_pair(a, b), i));
	}
	DFS(0, 0);
	cout << Answer << '\n';
	return 0;
}

djm03178 2년 전 1

n이 최대 100인데, 입력을 받을 때 a != b이면 V에 두 개씩의 원소를 넣고 있습니다. 따라서 V.size()는 최대 200이 됩니다.

이 크기만큼 루프를 돌면서 Select[i]에 접근하고 있는데, Select의 크기는 101이므로 배열의 범위를 초과하여 접근하게 됩니다. 이는 undefined behavior이므로 무슨 일이 벌어질지 알 수 없게 됩니다. https://www.secmem.org/blog/20... 를 참고하세요.

MAP의 유무로 정답이 갈리는 현실적으로 가능성이 높은 이유는, 메모리 주소상 Select 직후에 MAP이 오게 되어 '방파제'의 역할을 해주었기 때문일 수 있습니다. 이게 없다면 매우 중요한 다른 변수의 값을 건드렸을 가능성이 큽니다.

dltkdtn56 2년 전 0

감사합니다! 바로 이해하고 해결하였습니다

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

문제

문제

출처

ICPC

쓰이지도 않는 전역으로 선언된 배열에 따라 채점이 달라집니다.

dltkdtn56 2년 전 0

djm03178 2년 전 1

dltkdtn56 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말