글 읽기 - (주석있음) 질문글 반례는 다 통과하는데... C++ 다른 반례 부탁드립니다ㅠ

earlgrey94 3년 전 0

게시판에 올라와있는 반례 전부 통과하는데 도대체 어디가 틀린건지....

반례 부탁드립니다.

혹시 소스관련해서 조언해주실 수 있으면 냉정한 조언도 감사히 받겠습니다. :)

#include <iostream>
using namespace std;

short** paperMap;
short paperNumber[3] = { 0, };	//차례대로 -1, 0, 1

//같은 수만 적혔는지 확인
short IsSamePaper(short w, short h, int pLength) {
	short value = paperMap[w][h];
	for (int i = w; i < w + pLength; ++i) {
		for (int j = h; j < h + pLength; ++j) {
			if (paperMap[i][j] != value)
				return -2;
		}
	}
	return value;
}

void CuttingPaper(int pLength, short w, short h) {
	//크기가 1보다 작으면 재귀 탈출
	if (pLength >= 1) {
		short paperValue = IsSamePaper(w, h, pLength);
		//숫자가 같지 않으면 종이를 나눠서 다시 탐색
		if (paperValue == -2) {
			for (int i = 0; i < 3; ++i) {
				for (int j = 0; j < 3; ++j) {
					CuttingPaper(pLength / 3, w + (pLength / 3) * i, h + (pLength / 3) * j);
				}
			}
		}
		else
			paperNumber[paperValue + 1]++;	//paperValue는 -1부터 시작하므로 +1해서 넣어준다
	}
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;

	paperMap = new short*[n];
	for (int i = 0; i < n; ++i) {
		paperMap[i] = new short[n];
		for (int j = 0; j < n; ++j) {
			cin >> paperMap[i][j];
		}
	}

	CuttingPaper(n, 0, 0);

	for (int i = 0; i < 3; ++i)
		cout << paperNumber[i] << endl;
    return 0;
}

deepred 3년 전 1

3⁷* 3⁷ = 4,782,969로 short의 범위를 벗어납니다

ckdgus2482 3년 전 1

재귀함수의 기저사례가 잘못되었습니다.

페이퍼사이즈가 1일때 그냥 종료되는데, 페이퍼사이즈가 1인것도 그 수로 채워진 종이의 갯수를 증가시켜야합니다.

애초에 기저사례는 구간 내의 수가 모두 같은 경우이고, 페이퍼사이즈가 1인것은 이 경우에 포함되므로 페이퍼사이즈가 1인지를 따로 검사할 필요도 없습니다.

ckdgus2482 3년 전 1

다시보니 1 미만일때 종료였네요. deepred님 말대로 오버플로우가 틀린이유인것 같습니다.

그렇지만 21라인의 검사는 역시 무의미하므로 삭제하는게 좋습니다.

earlgrey94 3년 전 0

헐;;;;

최대한 메모리 크기 줄여보겠다고 short쓴거였는데... 멍청했네요ㅠㅠ

paperNumber 변수 short에서 int 로 수정하니까 바로 맞았어요ㅠㅠ

답변 달아주신 두 분 모두 감사합니다!

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

문제

문제

출처

ICPC

(주석있음) 질문글 반례는 다 통과하는데... C++ 다른 반례 부탁드립니다ㅠ

earlgrey94 3년 전 0

deepred 3년 전 1

ckdgus2482 3년 전 1

ckdgus2482 3년 전 1

earlgrey94 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말