[백준] 10448 - 유레카 이론

 

문제

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

삼각수 Tn(n ≥ 1)는 그림에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다.

또한 자연수 n에 대해 다음과 같은 공식을 만족한다.

$$ T_n = 1 + 2 + 3 + ... + n = n(n+1)/2 $$

1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다.

$$ 4 = T_1 + T_2 $$

$$ 5 = T_1 + T_1 + T_2 $$

$$ 6 = T_2 + T_2 = T_3 $$

$$ 10 = T_1 + T_2 + T_3 = T_4 $$

이 증명은 가우스가 다이어리에 “Eureka! num = Δ + Δ + Δ” 라고 적음으로써 유레카 이론으로 알려졌다.

 

임의의 자연수를 입력받아, 자연수가 3개의 삼각수의 합으로 표현될 수 있는지 없는지 판단하는 프로그램을 작성하라. 3개의 삼각수는 중복을 허용한다.

 

 

접근

메모이제이션과 중복조합을 활용하는 방식으로 접근했다.

 

1. 메모이제이션은 삼각수를 구하는 데 사용한다. 테이블과 값을 입력받아 테이블 내의 가장 큰 값이 값보다 같거나 커질 때까지 테이블을 갱신한다.

import sys

def memoization(memo, base):
    while memo[-1] < base:
        memo.append(memo[-1] + len(memo))
    return memo

memo = [0]
k = int(sys.stdin.readline())
memo = memoization(memo, k)

 

2. 삼각수를 세 번 선택할 수 있는 모든 경우의 수를 구할 수 있도록 중복 조합을 사용한다.

from itertools import combinations_with_replacement

tmp = [com for com in combinations_with_replacement(filtered, 3)]

 

 

풀이

구현 순서는 다음과 같다.

 

1. 테스트케이스의 개수 n을 입력받는다.

2. 테스트케이스 k를 입력받는다.

3. 메모이제이션으로 삼각수의 테이블 memo을 구한다. 초기 테이블은 미리 정의해 둔다.

4. 중복조합으로 구할 수 있는 경우의 수를 최적화할 수 있도록 테이블을 0보다 크고 테스트케이스의 값보다 작은 수로 필터링한다.

5. 중복조합을 활용하여 필터링한 값에서 값을 3번 선택한다.

6. 리스트 컴프리헨션을 이용해 중복조합의 합이 테스트케이스 k와 같은 것만 필터링한다.

7. 필터링한 리스트가 비어있지 않으면 1을, 그렇지 않으면 0을 출력한다.

 

전체 소스는 다음과 같다.

import sys
from itertools import combinations_with_replacement

# 삼각수 계산 함수
def memoization(memo, base):
    while memo[-1] < base:
        memo.append(memo[-1] + len(memo))
    return memo

# 테스트케이스 개수
n = int(sys.stdin.readline())

# 삼각수 테이블 초기화
memo = [0]

for i in range(n):
    # 테스트케이스 값
    k = int(sys.stdin.readline())
    # 삼각수 갱신
    memo = memoization(memo, k)
    # 삼각수 필터링
    filtered = [i for i in memo if 0 < i < k]
    # 중복조합을 이용해 값 3번 선택
    # 선택한 값의 합이 테스트케이스 k와 같은 것만 남긴다.
    tmp = [com for com in combinations_with_replacement(filtered, 3) if sum(com) == k]
    
    # 출력
    print(1 if tmp else 0)

 

 

참고 문서

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