[백준알고리즘] 10448번: 유레카 이론 -Python

[백준알고리즘] 10448번: 유레카 이론 -Python

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

10448번: 유레카 이론

문제 분류는 브루트포스로 되어있다.

 

문제를 푼 방식은 간단하다. 1번 만에 구할 수 있는 수와 2번 만에 구할 수 있는 수의 조합으로 주어진 수를 구할 수 있는 지를 확인하면 된다.

 

1번 만에 구할 수 있는 수는 주어진 T_n의 공식으로 구할 수 있다.

2번만에 구할 수 있는 수는 1번 만에 구할 수 있는 수에서 두 개를 선택해 합한 값들의 집합이다. 두 개 선택 시 중복이 허용될 수 있고 이 과정에서 1번 만에 구할 수 있는 수이면서 2번 만에 구할 수 있는 수도 구해진다.

 

3번 만에 구할 수 있는 수는 1번 만에 구할 수 있는 수와 2번 만에 구할 수 있는 수에서 각각 하나씩 선택해 합한 값과 같다. 마지막에 검색을 빠르게 해 주기 위해서 three만 딕셔너리로 해주었다.

t = int(input())
test = [int(input()) for _ in range(t)]
m = max(test)
one, two, three = [], [], {}

i = 1
while True:
    o = i*(i+1)//2
    if o > m: break
    one.append(i*(i+1)//2)
    i += 1

for i in range(len(one)):
    for j in range(i, len(one)):
        if one[i] + one[j] <= m:
            two.append(one[i] + one[j])
        else: break
two.sort()

for o in one:
    for t in two:
        if o + t <= m:
            three[o+t] = True
        else:
            break
        
for t in test:
    print(1 if three.get(t) else 0)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다