[Python] 백준 10448번(유레카 이론) 문제 풀이

 

triangle_number = [n*(n+1)//2 for n in range(1, 45)]
eureka = [0 for i in range(1001)]
for i in triangle_number:
    for j in triangle_number:
        for k in triangle_number:
            if i+j+k <= 1000:
                eureka[i+j+k] = 1
for i in range(int(input())):
    print(eureka[int(input())])

 

 https://claude-u.tistory.com/376

#325 백준 파이썬 [10448] 유레카 이론

 

 위 블로그를 참고했다고 쓰고 배꼈다고 읽는다. 브루트포스 알고리즘으로, triangle_number 리스트에 1000보다 작은 모든 삼각수를 넣은 뒤, 3중 반복문시간이 무려 O(n²)!으로 1000 이하의 삼각수로 나타낼 수 있는 수인지 아닌지를 eureka라는 리스트에 저장한다. 그러고 입력받은 수가 1000 이하의 삼각수의 합으로 나타내어진다면 1, 아니라면 0을 출력한다!