[백준/BOJ] python 10448번 유레카 이론

언어: python

번호: 10448

제목: 유레카 이론

등급: 브론즈 1

​

​

풀이 과정:

n 번째 요소에 Tn의 값이 들어있는 리스트 lst를 만든다. 3중 for 문으로 lst 값의 요소를 더하면서 유레카 이론이 성립하면 값을 출력한다.

​

​

코드:

1번째) 224ms

# 10448
lst = [0]*46

def func(n):    
    for i in range(1, 46):
        for j in range(i, 46):
            for k in range(j, 46):
                if lst[i] + lst[j] + lst[k] == n:
                    return 1
    return 0

for i in range(1, 46):
    lst[i] = lst[i-1]+i

t = int(input())
for _ in range(t):
    n = int(input())
    print(func(n))

 

 

2번째) 124ms

# 10448
lst = [(i*(i+1))//2 for i in range(45)]
check = [0]*1001

for i in range(1, 45):
    for j in range(i, 45):
        for k in range(j, 45):
            a = lst[i] + lst[j] + lst[k]
            if a <= 1000:
                check[a] = 1

t = int(input())
for _ in range(t):
    n = int(input())
    print(check[n])

 

​

메모:

두 코드가 비슷한 것 같은데 걸리는 시간은 거의 0.5배밖에 안된다. 그냥 값을 바꾸는 것보다 큰 리스트를 만들어서 요솟값을 1로 바꾸는 게 더 빠른 것 같은데 왜인지 모르겠다...