[ 10448 ] [ 완전 탐색 ] 유레카 이론

문제 설명

---

문제

삼각수 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+ T2or 6 = T3
• 10 = T1+ T2+ T3or 10 = T4

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

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

입력

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

출력

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

---

풀이 과정

1. 미리 삼각수를 1000까지 구해둔다. (입력 범위가 3~1000)이므로
2. 삼각수의 개수가 많지 않으므로 3중 반복문으로 모든 경우의 수를 구해준다.
   • i + j + k가 입력받은 값인지 검사
   • 그나마 조금이라도 효율성 높이기 위해 i, j, k 각각이 입력받은 값보다 크면 continue
3. i + j + k가 입력받은 값이 된다면 1, 되지 않는다면 0 출력

---

소스 코드

import sys

start = 1
add = 2
Triangle = []
while True:
    Triangle.append(start)
    start += add
    add += 1
    if start >= 1000:
        break

def check(a, Triangle):
    for i in Triangle:
        if i >= a: continue
        for j in Triangle:
            if j >= a: continue
            for k in Triangle:
                if k >= a: continue
                if i + j + k == a:
                    return True

    return False


count = int(sys.stdin.readline().rstrip())
for i in range(count):
    n = int(sys.stdin.readline().rstrip())
    if check(n, Triangle):
        print(1)
    else:
        print(0)