[BOJ] 10448 - 유레카 이론 (🥉 브론즈 1티어)

사용 언어: Python3

문제

유레카 이론

풀이

나의 풀이

from math import sqrt
from math import modf
from itertools import combinations_with_replacement # 중복조합

# k가 삼각수인지 아닌지
def isTri(k):
    a, b = (-1+sqrt(1+8*k))/2, (-1-sqrt(1+8*k))/2
    if (a > 0 and modf(a)[0] == 0) or (b > 0 and modf(b)[0] == 0): # modf(a)[0]: 소수부분, modf(a)[1]: 정수부분
        return True
    return False

# 정확히 3개의 삼각수의 합으로 표현될 수 있는지
N = int(input())
for _ in range(N):
    K = int(input())
    # 3개의 수로 나누기
    lst = [x for x in range(1, K-1)]
    for val in combinations_with_replacement(lst, 3):
        if sum(val) == N and all(isTri(x) for x in val): # 나눈 3개의 수 모두가 삼각수이면 1
            print('1')
            break
    else:
        print('0')

• 테스트 케이스: 성공
• 제출 결과: 시간 초과 🥵

다른 풀이

triangle = [] # 삼각수
eureka = [0] * 1001 # 3개의 삼각수의 합으로 이루어진 유레카수

# ✅ 미리 1000 이하의 모든 삼각수를 구한다
for i in range(1, 1000):
    tmp = i*(i+1)//2
    if tmp <= 1000: triangle.append(tmp)
    else: break

# ✅ 3개의 삼각수의 합으로 표현될 수 있는 유레카수를 체크한다 (3개의 삼각수가 같아도 된다)
for x in triangle:
    for y in triangle:
        for z in triangle:
            if x + y + z <= 1000: eureka[x + y + z] = 1

N = int(input())
for _ in range(N):
    K = int(input())
    print(eureka[K])

• 테스트 케이스: 성공
• 제출 결과: 성공

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기