UVa. 112, PKU 1145. Tree Summing. AC get!

main() { int st[10000], len, i, sum, lev, cp, f; char temp; while (scanf("%d", &len) != -1) { lev = 0; sum = 0; f = 0; while (1) { while ((temp = getchar()) != '(') { if (temp == ')') { f++; if (f == 4) { if (sum == len) { cp = 1; } } sum -= st[lev--]; if (!lev) { goto a; } } } lev++; f++; if (scanf("%d", &i)) { st[lev] = i; sum += i; f = 0; continue; } else { st[lev] = 0; while (getchar() != ')'); f++; if (f == 4) { if (sum == len) { cp = 1; } } sum -= st[lev--]; } a: if (!lev) { if (!cp) { puts("no"); } else { puts("yes"); cp = 0; } break; } } } return 0; }

ANSI C 기준 컴파일러에서 동작하는 코드입니다.

VS의 경우는 6.0에서만 가동됩니다.

스타팅의 '('를 기준으로 트리 노드 레벨을 설정해 최초 시작시 1, 최후 노드 레벨이 0이 되면 탈출하도록

하면서 처리했습니다.

노드레벨이 증가할때(루트에서 멀어질 때) 합에 노드의 값을 더하고, 노드레벨이 감소할 때(루트에 가까워질때)

합에서 기존 노드의 값을 빼는 방식으로 진행하면서, 양쪽 자식노드가 모두 없을 때

(()()꼴일때)의 합을 먼저 입력받은 비교대상과 비교해 맞는지 아닌지 여부를 처리하게 했습니다.

여러 줄에 걸쳐 받아야 하는데다가, 한 줄에 괄호하나 딸랑 있는 경우도 존재하기 때문에

한 글자씩 받아 처리했으며(getchar로 돌렸지요....), scanf가 숫자가 아닌 값을 받았을때 false를 반환한다는

점을 이용해 빈 트리노드인지 아닌지를 판별했습니다.

UVa 기준 상위 랭크 43위 기록된 코드입니다.