방구석 사색

둘레의 길이가 자연수 $n$이고, 세 변의 길이가 모두 자연수이며, 합동이 아닌 삼각형의 개수를 구하시오.시간 복잡도가 무엇인지 이해하는 데에는 [삼각형 만들기] 만한 문제가 없을 것입니다. 순진하게 시간 복잡도가 $O\left(n^3\right)$인 풀이로 시작해서 조금 다르게 접근하거나 더 좋은 풀이를 연구하며 $O\left(n^2\right)$과 $O(n)$을 거쳐 입력값의 크기에 상관없이 $O(1)$, 즉 단번에 계산할 수 있는 풀이가 존재하기 때문이죠. 또한, 복잡하고 어려운 자료 구조나 알고리즘을 요구하지 않아 간단한 조건문과 반복문만으로 정답을 계산할 수 있고, 실제로 프로그래밍을 통해 문제를 해결할 때 주어진 제한 시간 내에 풀 수 있는 입력의 범위를 넓히는 사고 과정을 잘 보여..