문제

링크

풀이

브론즈 문제인데 생각보다 시간이 오래 걸린 문제였다...

1. 1~1000사이의 숫자 중 정확히 3개의 삼각수의 합으로 표현될 수 있는 정답지를 만든다.

2. 정답지를 통해 입력받은 K가 3개의 삼각수의 합으로 표현될 수 있는지 확인 후 출력한다.

쉽게 말하면 answer는 정답지이다. triangleNum은 삼각수들의 모임이다. triangleNum은 1000이하까지만 구해주면 된다. 왜냐하면 3개의 삼각수를 더할 때 삼각수 중 하나라도 1000초과이면 1000이 넘어버리기 때문이다. (당연한 말이다...)

코드

import sys

answer = [0] * 1001
triangleNum = []
for i in range(1, 45):
    triangleNum.append(i * (i + 1) // 2)

for one in triangleNum:
    for two in triangleNum:
        for three in triangleNum:
            if one + two + three <= 1000:
                answer[one + two + three] = 1

# print(answer)

input = sys.stdin.readline
T = int(input())
K = []
for _ in range(T):
    K.append(int(input()))

for target in K:
    print(answer[target])