**🔗 참고 문제** → [<https://www.acmicpc.net/problem/17626>](<https://www.acmicpc.net/problem/17626>)      // 클릭 시 이동

# 📌 BST 전위 순회 -> 후위 순회 변환

이진 탐색 트리(Binary Search Tree)의 전위 순회 결과만 주어졌을 때, 실제 노드를 만들지 않고
배열 + 범위(Min, Max) + 전역 Idx 로 후위 순회를 바로 출력하는 방식

- 🔑 현재 값이 이 서브트리에 들어올 수 있는 범위인가 체크가 핵심 

🎯 문제 유형

• 제곱수 합 분류
• 최소 개수 분류

📋 핵심 정리

1. 라그랑주 4제곱수 정리

• 모든 자연수는 4개 이하의 제곱수 합으로 표현 가능
• 즉, 어떤 자연수 n 도 항상 n = a² + b² + c² + d² 형태로 표현 가능
• 여기서 a, b, c, d 는 0도 가능

정리하자면,
라그랑주 4제곱수 정리에 따르면
1. 어떤 제곱수 합도 개수가 5개를 넘을 수 없다.
2. 즉, 제곱수 합의 최소 개수는 항상 1, 2, 3, 4 중 하나이다.

1. 르장드르 3제곱수 정리

• 자연수 n 이 n=4^a(8b+7) 형태이면, n 은 1, 2, 3개의 제곱수 합으로 표현할 수 없다.

예시로,
1. 7 = 4^0(8×0 + 7)
2. 15 = 4^0(8×1 + 7)
3. 28 = 4^1(8×0 + 7)

이런 수들은 1, 2, 3개의 제곱수 합으로 표현이 불가능하다.

🚮 선입견을 버리자