boj

백준 10448 유레카 이론 -python

boj-10448

Posted by 동식이 블로그 on August 10, 2019

백준 10448 유레카 이론 -python


너무 어렵지 않은 완전 탐색 문제집 3번문제 !!


문제풀이

  • 모든 삼각수를 구해놓고 그중 3개로 구성된 순열들의 값을 비교
  • K의 범위가 1000이하인 수이기 때문에 1000이하인 삼각수를 모두 구했었는데 다시 생각해보니 합이 1000이하여야 한다는걸 깨닳았다.
  • 그래도 시간초과가 나서 순열을 구하는 중 3개를 찾으면 바로 리턴해줬다.


code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import itertools

def threeNum(n):
    return int(n*(n+1)/2)

arr = []
for i in range(1,1001):
    if(threeNum(i) > 1000):
        break
    arr.append(threeNum(i))
N = int(input())
n = []
for _ in range(N):
    n.append(int(input()))

res = 0
for x in n:
    for i in itertools.product(arr,repeat=3):
        if(sum(i) == x):
            res = 1
            break
    print(res)
    res = 0