[브론즈 1] 백준 10448 - 유레카 이론 (파이썬)

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

풀이

D = [0] * 50
D[0] = 1
D[1] = 3
for i in range(1, 50):
    D[i] = D[i - 1] + i + 1

삼각수를 생성한다.

for combination in combinations(D, 3):
    if sum(combination) == N:
        found = True
        break

• combinations(D, 3)는 중복 없이 3개를 뽑아 더한 것이 N과 같은지 확인
• 중복이 안되기 때문에 예를 들어 (3, 3, 3) 같은 케이스는 이 조건에 안 걸림

for combination in combinations(D, 2):
    if combination[0] * 2 + combination[1] == N:
        found = True
        break
    if combination[0] + combination[1] * 2 == N:
        found = True
        break

if N % 3 == 0 and N // 3 in D:
    found = True

• 2개 조합에서 한 쪽을 2번 더해 3개의 합 만들기
• 혹은 하나를 3번 더한 경우도 따로 처리 (즉, 3의 배수이면서 삼각수일 때)

코드

# 백준 10448 - 유레카 이론
# 분류 : 브루트 포스

from itertools import combinations

T = int(input())

D = [0] * 50
D[0] = 1
D[1] = 3
for i in range(1, 50) :
    D[i] = D[i - 1] + i + 1

for _ in range(T) :
    N = int(input())

    found = False
    for combination in combinations(D, 3) :
        if sum(combination) == N :
            found = True
            break
    
    for combination in combinations(D, 2) :
        if combination[0] * 2 + combination[1] == N :
            found = True
            break
        if combination[0] + combination[1] * 2 == N :
            found = True
            break
    
    if N % 3 == 0 and N // 3 in D :
        found = True
    
    if found :
        print("1")
    else :
        print("0")

from itertools import combinations

T = int(input())

D = [0] * 50
D[0] = 1
for i in range(1, 50) :
    D[i] = D[i - 1] + i + 1

E = [[False] * 4 for _ in range(1001)]
E[0][0] = True
for i in range(1, 1001) :
    for j in range(1, 4) :
        E[i][j] = False

        for k in D :
            if i < k :
                break
            E[i][j] |= E[i - k][j - 1]

for _ in range(T) :
    N = int(input())

    if E[N][3] :
        print("1")
    else :
        print("0")