글 읽기 - 출력초과 해결 못하겠습니다..

dksworhkd123 4년 전 0

우선 인오더의 인덱스정보, 포스트오더의 인덱스 정보를 이용하여 문제를 풀었습니다.

왼쪽자식 오른쪽 자식 모두 있다 생각하고 인덱스 정보들을 먼저 구했구요

왼쪽자식이 있을때 혹은 오른쪽 자식이 있을때 해당 자식을 다시 재귀하는 방식으로 풀었습니다만

왜 계속 출력초과가 발생하는지 모르겠습니다..

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

using namespace std;

int n, In[100000] = { 0, }, Post[100000] = {0,};
void solve(int is, int ie,int ps, int pe) 
{
	if (is == ie && ps == pe) // 한개일 경우
	{
		printf("%d ", In[is]);
		return; 
	}
	else
	{
		int root = Post[pe];
		int InRootIdx;
		printf("%d ", root);
		for (int i = is; i <= ie; i++) 
		{
			if (In[i] == root) 
			{
				InRootIdx = i;
				break;
			}
		}
		int ile = InRootIdx - 1;
		int irs = InRootIdx + 1;
		int postLe = ps + (ile -is + 1) -1;
		int postRs = postLe + 1;
		//위의식에서 idx 구할때를 토대로 예외처리
		/*
		왼쪽자식이 없을때 ile이 -1이됨
		오른쪽 자식이 없을때 포스트오더의 루트가(마지막 pe) 오른쪽자식이 시작과끝이됨
		*/
		if(ile>=0) solve(is, ile, ps, postLe); //왼쪽자식 있을때
		if(postRs!=pe)solve(irs, ie, postRs, pe-1); //오른쪽 자식 있을때
	}
}

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", In + i);
	for (int i = 0; i < n; i++) scanf("%d", Post + i);
	solve(0, n - 1, 0, n - 1);
	printf("\n");
	return 0;
}

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

문제

문제

출처

ICPC

출력초과 해결 못하겠습니다..

dksworhkd123 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말