[코딩테스트] 백준 유레카 이론 파이썬(python)

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

10448번: 유레카 이론

def cal_T():
  n = 1
  array = []
  while True:
    number = int(n * (n+1) / 2)
    if number > 1000:
      break
    array.append(number)
    n+=1
  return array
def ureka(k, T):
  for i in range(len(T)):
    for j in range(len(T)):
      for n in range(len(T)):
        if (T[i] + T[j] + T[n]) == k:
          return 1
  return 0

T = cal_T()
for _ in range(int(input())):
  k = int(input())
  print(ureka(k, T))

최대 3개의 삼각수(T)의 합으로 k가 표현이 될 수 있으니
3중 반복문을 사용하여 3개의 자연수를 찾아서 합하여
표현될 수 있으면 1, 없으면 0을 반환하는 함수 ureka를 작성하였습니다.

 

이때 계산 전에 k까지의 수 중 모든 T를 구하고 반복문을 돌리려 했지만 시간초과가 나와서 적정한 T를 찾아야했습니다.

• 구해도 겨우 1000개라고 생각했지만 3중 반복문을 돌리면 $1000^{3}$ 이어서 많은 시간이 걸렸습니다.

T의 크기를 줄이기 위하여 삼각수를 계산하는 공식 $\frac{n(n+1)}{2}$ 을 이용하여 도출된 number가 테스트케이스로 주어지는 최대값 1000을 넘지않을 때까지 수를 저장하여 T를 구하였습니다.
위의 과정을 cal_T함수로 작성하였습니다.

 

위의 두 함수를 이용하여 올바른 결과값을 반환하여 문제를 해결하였습니다.