글 읽기 - 잘 출력되는데 제발 왜 틀린지좀 알려주세요

jjy1715 6년 전 0

부탁드립니다. 고수님들. 뭐가 문제인가요

#include<iostream>

int n;  //0부터 시작
long long r;  //행
long long c;  //열
long long count = -1;

long long zecop(int n) {

	long long result = 1;

	for (int i = 1; i <= n; i++) {
		result = result * 2;
	}
	return result;
}

long long car(long long x, long long y, long long size) {

	if (r == x && c == y) {
		count = count + 1;
		return count;
	}
	else if (r == x && c == y + 1) {
		count = count + 2;
		return count;
	}
	else if (r == x + 1 && c == y) {
		count = count + 3;
		return count;
	}
	else if (r == x + 1 && c == y + 1) {
		count = count + 4;
		return count;
	}

	count = count + 4;

	if (y + 2 < size) {
		car(x, y + 2, size);
	}
	else if (x + 2 < size) {
		car(x + 2, 0, size);
	}
}

int main(void) {

	scanf("%d %lld %lld", &n, &r, &c);

	long long result;
	long long size = zecop(n);
	result = car(0, 0, size);
	printf("%lld\n", result);

	return 0;
}

djm03178 6년 전 0

warning C4715: 'car' : 모든 제어 경로에서 값을 반환하지는 않습니다.

잘 되리라는 보장은 없어보이네요. VS 2013에서는 답이 잘 나오는 것을 확인했지만, 원칙적으로는 car 함수가 36번째 줄까지 도달하면 절대 값을 반환하지 않으니까요.

VS에서는 아마도, 함수가 아무 값을 리턴하지 않으면 마지막으로 어떤 함수가 리턴한 값을 사용하게끔 해놓은 모양인데, 다른 컴파일러에서도 그러리라는 보장은 없죠.

jjy1715 6년 전 0

제가 컴파일러에 대한 이해가 부족해서 그러는데, 그러면 어떤식으로 수정해야하나요? 아예 알고리즘을 뜯어고쳐야하나요?

djm03178 6년 전 0

그냥 return car(x, y + 2, size); 랑 return car(x + 2, 0, size); 라고 써주면 되겠죠. 경고는 남아있겠지만 논리적으로 둘 중 하나는 반드시 걸리니까 상관 없겠고요.

jjy1715 6년 전 0

바꿔도 틀리네요 ㅠㅠ 제가 보니까 n이 11이상되면 스택오버플로우가 발생하는데 이거 왜 그런건가요?

djm03178 6년 전 0

다시 쭉 읽어봤는데, 방법이 잘못됐네요.

지금 코드는, 4칸씩 기준으로 해서 무조건 오른쪽으로 끝까지 쭉 간 다음에 두 줄 건너서 다음 탐색을 시작하는 방식으로 구현하고 있는데, 문제를 잘 보면 그렇게 되는 게 아닙니다.

가령, 3 0 4로 입력이 들어오면 답은 16이 되어야죠. 문제의 그림을 잘 보시면 알 수 있습니다.

그리고 스택 오버플로가 발생하는 건, 배열의 크기가 커질 때에 이렇게 순차탐색을 하면 재귀호출의 깊이가 엄청나게 깊어지기 때문입니다. 함수에 대한 정보나 선언된 지역변수들이 모두 스택에서 차곡차곡 쌓여가기 때문에, 이를 견뎌내지 못합니다.

사실 이 문제가 순차탐색으로 풀 수 있는지는 모르겠는데, 가능하다고 하더라도 최악의 경우에는 시간초과가 날 수밖에 없다고 보입니다. 분할 정복을 하셔야 합니다.

jjy1715 6년 전 0

시간초과나는건 그렇다 칠수 있는데요,

3 0 4가 입력으로 들어왔을때 왜 답이 16이 되나요?

0 1 4 5 8 9 12 13

2 3 6 7 10 11 14 15

답은 8이 되는거 아닌가요?

jjy1715 6년 전 0

아 그림을 잘못봤군요....

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