[백준/Python3] 10448번: 유레카 이론 - 완전탐색

유형별로 문제를 풀어볼 예정이다.

해당 문제는 완전탐색 유형의 문제이다.

 

유레카 이론 다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

15689

9158

7161

57.490%

문제

삼각수 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

 

 

---

[코드]

num=int(input())
x = []
T=[i*(i+1)//2 for i in range(1,46)] #45*46/2 = 1035

def can_divide(num):
    for i in T:
        for j in T:
            for k in T:
                if (i+j+k == num):
                    return 1
    return 0
    
    
for i in range(num):
    x.append(int(input()))
    
for i in x:
    y=can_divide(i)
    print(y)

 

 

---

[알게된 점]

def T(num):
    sum=0
    for i in range(num+1):
        sum+=i
    return sum

def can_divide(num):
    for i in range (1,num):
        for j in range (1, num):
            for k in range(1,num):
                if (T(i)+T(j)+T(k) == num):
                    return 1
    return 0

원래는 다음과 같이 코드를 작성했지만 실행시간이 너무 오래걸려 실패하였다.

 

T=[i*(i+1)//2 for i in range(1,46)]

따라서 삼각수를 배열로 만들어 대입했더니 빠른 시간내에 결과값을 낼 수 있었다~