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

#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 해보겠습니다.

성공하면 이 란에 올리죠.