[Brute Force] 백준 10448 유레카 이론 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

10448번: 유레카 이론

 

 

 

2. 문제 풀이

Tn = 1 + 2 + 3 + 4 ... + n = n(n+1)/2

 등차가 1인 수열의 합으로 표현되는 수를 '삼각수'라고 합니다. 정수 K가 주어졌을 때, 세 삼각수의 합으로 표현할 수 있는지를 판별해야 합니다.

 

2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

[Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

 세 삼각수의 모든 조합을 고려해서 K가 될 수 있는지를 판별해야 합니다. 파이썬에서는 itertools의 product 함수를 이용하면 쉽게 중복조합을 구할 수 있습니다.

 

itertools.product(lst, repeat=n): lst에서 중복허용해서 n개씩 뽑을 모든 경우의 수 (순서고려 X)

 

 

 

3. 코드

from itertools import product
import sys
input = sys.stdin.readline

#삼각수
triangle_num = []
total = 0
for i in range(1, 9999):
    total += i
    triangle_num.append(total)

    # 최대 K는 1000
    if total > 1000:
        break

# 중복조합을 이용한 세 삼각수의 합
case = set(sum(x) for x in product(triangle_num, repeat=3))
case = sorted(case)

 삼각수를 구하고, 중북조합으로 삼각수 3개의 합을 구합니다. 세 삼각수의 합이 같은 조합이 여러 개일 수 있으므로, 집합 set으로 중복으로 제거해줍니다.

 

 

#입력
T = int(input())
for _ in range(T):
    K = int(input())
    for i in case:
        #세 삼각수 합과 같으면 1
        if K == i:
            print(1)
            break

        #세 삼각수 합을 넘어서면 0
        if K < i:
            print(0)
            break

 크기가 작은 세 삼각수의 합부터 K와 비교합니다. K와 같으면 세 삼각수의 합으로 표현할 수 있습니다. 반면 세 삼각수의 합이 K를 넘어서면, 그 수는 세 삼각수로 표현하지 못합니다.