글 읽기 - 1391 종이접기 반례부탁드려요 ㅠㅠ

myabc17 4년 전 0

예제 케이스랑 문제에 있던 1,2,3,4,5,6,7도 해보고

제가 임의로 6 4 2 1 3 5 도 해봤는데 답은 맞게 나오는데 제출만 하면 틀렸다고 나오네요... 혹시 반례가 있을까요??

아니면 2차원 배열크기를 2001x2001로 해서 바로 터지는 건가요?? 제 Visual Studio 2015 에서는 처음에 바로 터지긴 했는데 스택예약크기 바꿔서 돌아가게 만들었습니다. 이렇게 하면 안되는 건가요?ㅠㅠ 도와주세요

+수정

10 9 8 7 6 1 2 3 4 가 되길래 아 이게 틀렸었구나 해서 고쳤습니다. 근데 이젠 시간 초과가 뜨네요..ㅎ

풀이가 하나도 없는데 혹시 이거 linked list로 풀어야하나요?

#include <iostream>
#define MAX 2001

using namespace std;

bool solve(int stack[][MAX], int top[], int n);
void fold(int stack[][MAX], int top[], int start, int length);

int T, N;
int start_point, end_point;

int main()
{
	cin >> T;

	for (int i = 0; i < T; i++) {
		cin >> N;
		int stack[MAX][MAX] = { { 0, } };
		int top[MAX] = { 0, };

		for (int j = 1; j <= N; j++) {
			cin >> stack[j][1];
			top[j] = 1;
		}
		if (solve(stack, top, N))
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	return 0;
}
bool solve(int stack[][MAX], int top[], int n)
{
	int len = n;
	start_point = 1;
	end_point = n;

	while (start_point != end_point) {
		for (int i = start_point; i < end_point; i++) {
			// 연속된 숫자의 종이일 경우 ex) 4,5  or  5,4   접는다.
			if (stack[i][top[i]] == (stack[i + 1][top[i + 1]] + 1) || stack[i][top[i]] == (stack[i + 1][top[i + 1]] - 1)) {
				fold(stack, top, i, end_point - start_point + 1);
				break;
			}
		}
	}
	for (int i = 1; i <= len; i++) {
		if (stack[start_point][i] != i)
			return false;
	}
	return true;
}
void fold(int stack[][MAX], int top[], int start, int length) {
	int j = start;
	if (start >= length / 2) {
		for (int i = start + 1; i <= length; i++) {
			// 접는부분에 접히는 부분 숫자 위로 올리기
			while (top[i] != 0) {
				stack[j][++top[j]] = stack[i][top[i]--];
			}
			j -= 1;
		}
		end_point = start;
	}
	else {
		j = start + 1;
		for (int i = start; i > 0; i--) {
			// 접는부분에 접히는 부분 숫자 위로 올리기
			while (top[i] != 0) {
				stack[j][++top[j]] = stack[i][top[i]--];
			}
			j += 1;
		}
		start_point = start + 1;
	}
}

djm03178 4년 전 0

백준도 스택 메모리 제한은 따로 없습니다. 배열 크기 때문에 터진다면 틀렸습니다가 아니라 곧바로 런타임 에러 내지는 메모리 초과가 날 것입니다.

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

문제

문제

출처

ICPC

1391 종이접기 반례부탁드려요 ㅠㅠ

myabc17 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말