C. Eureka Theorem

3 이상 1000 이하 자연수 $K$가 주어졌을 때, $K$를 정확히 3개의 삼각수의 합으로 표현할 수 있는지 판별하는 문제다.

$K$는 1000 보다 크지 않으므로, 1000 이하의 삼각수 44개를 이용하여, 삼 중 for문으로 가능한지 판별할 수 있다. 테스트케이스 별로 삼 중 for문을 쓰면 시간 초과 될 여지가 있으므로, 전처리를 하면 좋다.

#include <stdio.h> int T,A[45],D[1001]; int main() { int i, j, k; for (i=1;i<45;i++) A[i] = i*(i+1)/2; for (i=1;i<45;i++) for (j=i;j<45;j++) for (k=j;k<45;k++) if (A[i]+A[j]+A[k] < 1001) D[A[i]+A[j]+A[k]] = 1; for (scanf("%d", &T);T--;){ scanf("%d", &k); printf("%d\n", D[k]); } }