서론

브루트포스 문제입니다.
처음엔 삼각수의 배열을 먼저 만들어놓고 테스트케이스에서 입력 받을 때마다 조건에 성립하는지 계산했는데,
이 방법이 시간초과가 나길래 정답 배열도 미리 만들어서 통과하였습니다.

난이도

브론즈 1

---

문제

조건

시간 제한	메모리 제한
1 초	256 MB

---

삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다.

[그림]

자연수 n에 대해 n ≥ 1의 삼각수 Tn는 명백한 공식이 있다.

Tn = 1 + 2 + 3 + ... + n = n(n+1)/2

1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어,

4 = T1 + T2
5 = T1 + T1 + T2
6 = T2 + T2 or 6 = T3
10 = T1 + T2 + T3 or 10 = T4
이 결과는 증명을 기념하기 위해 그의 다이어리에 “Eureka! num = Δ + Δ + Δ” 라고 적은것에서 유레카 이론으로 알려졌다. 꿍은 몇몇 자연수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 궁금해졌다. 위의 예시에서, 5와 10은 정확히 3개의 삼각수의 합으로 표현될 수 있지만 4와 6은 그렇지 않다.

자연수가 주어졌을 때, 그 정수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 없는지를 판단해주는 프로그램을 만들어라. 단, 3개의 삼각수가 모두 달라야 할 필요는 없다.

---

입력

프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어있다.

---

출력

프로그램은 표준출력을 사용한다. 각 테스트케이스에대해 정확히 한 라인을 출력한다. 만약 K가 정확히 3개의 삼각수의 합으로 표현될수 있다면 1을, 그렇지 않다면 0을 출력한다.

---

예시

예제 입력 1

3
10
20
1000

예제 출력 1

1
0
1

---

풀이

1. 삼각수의 배열을 먼저 초기화한다.
2. 정답 배열을 생성한다(k의 범위가 1000까지이기 때문에 1000까지 가능한 크기를 생성했다.)
3. 3중 반복문을 통해 삼각수 배열에서 세 개의 숫자를 임의로 선택한다.
4. ans의 선택한 세 숫자 합 인덱스를 1로 만들어준다.

코드

import sys
input = sys.stdin.readline

t = [i * (i + 1) // 2 for i in range(1, 46)]	# 삼각수 배열
ans = [0] * 1001								# 정답 배열, k의 최대 숫자가 1000

for i in t:
    for j in t:
        for k in t:					# 삼각수의 세 숫자 선택
            if i + j + k <= 1000:	# 인덱스 에러 방지를 위해 1000까지만 계산
                ans[i + j + k] = 1	# 세 숫자의 합이 존재하면 1

for _ in range(int(input())):
    print(ans[int(input())])		# 미리 초기화해둔 배열에서 숫자만 입력

실행 결과