[BOJ 10448] 유레카 이론 (Python)

https://www.acmicpc.net/problem/10448

10448번: 유레카 이론

브론즈 1문제이다. 

 

유레카 이론은 삼각수의 합을 통해서 모든 자연수를 표현할 수 있다고 한다.

하지만 실제로 표현하지 못하는 수도 존재하는데 이러한 수를 구별하는 프로그램을 만드는 것이다. 

 

즉 , 임의의 자연수를 $T_{i} + T_{j} + T_{k}$ 또는 $T_{i} + T_{j}$ 또는 $T_{i}$ 로 표현할 수 있는 경우와 아닌경우를 구분하는 것이다. 이 문제의 해법은 생각보다 간단했다. 판별해야하는 수 자체가 최대 1000의 값으로 작은 수이고, 삼각수의 45번째 이내의 항으로 표현할 수 있으니 그냥 냅다.. 되는 수를 하나하나 찾아 내면 되는 것이다.

 

 

import sys

# 삼각수 배열
triangular_number = [(i*(i+1))//2 for i in range(1, 46)]
eureka_num = [False, True, True] + [False]*998

for i in triangular_number:
    for j in triangular_number:
        for k in triangular_number:
            if i + j + k <= 1000:
                eureka_num[i+j+k] = True

t = int(input())

for _ in range(t):
    k = int(sys.stdin.readline())
    if eureka_num[k]:
        print(1)
    else:
        print(0)