PKU [1145], UVa [112]. Tree Summing. [AC]

알 수 없는 사용자 2008. 9. 8. 21:25

#include <stdio.h>

enum finder { EMPTY, FAIL, FIND };
typedef enum finder checking;

checking checker( int sum, int isum );
void input1(void);
void input2(void);
int tree_is_empty(void);

int main()
{
	int input_sum;
	int sum = 0;
	checking result;

while((scanf("%d",&input_sum)) != EOF)
		{
			result = checker(sum, input_sum );
			if ( result == FIND ) 
			{
				printf("yes\n" );
			} 
			
			else 
			{
				printf("no\n" );
			}
		}

return 0;
}

checking checker( int sum, int isum )
{
	int nod;
	checking result;
	checking l_tree, r_tree;

input1();

if ( tree_is_empty() ) 
	{
		result = EMPTY;
	} 
	
	else 
	{
		scanf("%d", &nod);

sum += nod;
		l_tree = checker( sum, isum );
		r_tree = checker( sum, isum );

if (l_tree == EMPTY && r_tree == EMPTY && sum == isum) 
		{
			result = FIND;
		} 
		
		else if (l_tree == FIND || r_tree == FIND)
		{
			result = FIND;
		} 
		
		else
		{
			result = FAIL;
		}
	}

input2();

return result;
}

void input1()
{
	char a;

a = getchar();

while ( a != '(' )
	{
		a = getchar();
	}
}

void input2()
{
	char a;

a = getchar();
	
	while ( a != ')' )
	{
		a = getchar();
	}
}

int tree_is_empty()
{
	char a;

a = getchar();
	
	ungetc(a, stdin);

if(a == ')')
	{
		return 1;
	}

else
	{
		return 0;
	}
}

In PKU judge system.

In UVa judge system.

씁 -_-;

결국 저번 솔루션 재탕이군요.

보시면 알겠지만... getchar 로 한 문자씩 받아서 검사합니다.

단, '(' 과 ')' 을 처리하는 입력 루틴은 따로따로 만들어 놨죠.
그리고 트리가 EMPTY 인지 판별하는 루틴 역시 따로 존재합니다.

좀 더 코드 가독성을 좋게 만들기 위해 열거형도 사용했습니다.
각기 EMPTY , FAIL, FIND 로 명명했고, 만악 트리의 leaf 에서 합계를 찾아내면 FIND를 리턴합니다.

일단... 만약 input1 에서 '(' 를 받고 나서 바로 ')' 라는 값이 온다면, 이 트리는 EMPTY 입니다.
따라서, tree_is_empty 함수를 호출합니다. 이를 검사하기 위한 목적입니다.

이후 57행에서 말단 노드에 도달했을 때 처음 입력값과 같다면... 합계를 찾은 것이겠죠. FIND 를 리턴합니다.

그리고 tree_is_empty 함수에선 독특한 놈 하나를 볼 수 있을겝니다 -_-;; ungetc죠.

Runtime Error 를 해결하기 위해 사용했습니다.-_-;; 빼시면 아마도 TL 걸릴겁니다.
예전 dlbo군의 말대로 버퍼에서 '\n' 과 스페이스가 나온다면 RE 걸리더군요.
이걸 해결하기 위해...무식하게 ungetc를 쓴 거죠.

하지만 -_-;;; 이 솔루션은 옵티마이즈된 솔루션이 아닙니다.

만약 말단노드에서 값을 찾아서, FIND 를 리턴한다 할지라도 프로그램은 멈추지 않고 마지막 노드까지
탐색합니다 -_-;;;;;;;;;;;

해결하기 위해 이 FIND 값을 바로 main으로 호출시켜 보려고 해봤지만 실패했구요.

앞서 언급했다시피, 이 솔루션은 전북대 컴퓨터동아리 ALPS의 솔루션 중 하나와 90% 이상 동일합니다.
열거형의 사용. 루틴의 갯수와 기능. 그리고 기본적인 알고리즘까지 모두 다. -_-;

그래서 지금 굉장히 기분 이상하군요 -_- 쩌업.

무슨 수를 써봐도 도저히 다른 방법이 생각 안납니다;
결국 이 솔루션과 하등 다를바가 없어지는 안습한 사태가 -_-;

일단 올리긴 하겠습니다만... 계속해서 resolve 해보겠습니다.

성공하면 이 란에 올리죠.