Project Euler Problem 577

https://projecteuler.net/problem=577

 

난이도 : 20%

 

다음 그림처럼 한 변의 길이가 $n$ 인 정삼각형을 한 변이 $1$인 정삼각형 $n^2$ 개로 나눈 상황을 생각해 보자. 

 

이때, 저 중 6개의 점을 이어서 만들 수 있는 정육각형의 개수를 $H(n)$ 이라고 하자. $\sum H(n)$ 을 구하는 문제.

---

$H(3) = 1$이 주어졌는데, 이는 어렵지 않게 알 수 있다. 그림도 나와 있고.

그리고 나서도 $H(4) = 3$, $H(5) = 6$ 까지는 확실하고... 

삼각수 $T_n$을 이용하면, 한 변의 길이가 1인 정육각형이 $T_{n-2}$ 개 있다는 것을 알 수 있다. 몇 개 더 그려 보기로 하자.

$n = 6$ 케이스의 그림을 열심히 그려 보면, 한 변의 길이가 1인 정육각형을 10개, 한 변이 2인 정육각형 1개를 셀 수 있는데, 주어진 $H(6)$ 은 12이다. 사실 처음에 찾기 좀 힘든 경우가 하나 더 있어서....

이 경우를 찾는데 굉장히 오래 걸린거 같다. 아무튼 한 변의 길이가 $\sqrt{3}$ 인 정육각형 하나가 있어서 총 12개이다.

 

여기서 좋은 관찰을 하나 할 수 있는데,

한 변의 길이가 $t$ (정수) 인 정육각형에서, 변 양쪽 사이에 $t-1$개 점이 들어가 있는데, 이걸 순서대로 잘 이어 주면 새로운 정육각형을 얻는다. 즉, 예를 들어 $n = 9$에서 한 변의 길이가 3인 정육각형은 가운데 2개씩 점이 추가로 있어서, 이걸 잘 이어 주면 새로운 정육각형 2개를 더 얻을 수 있다.

이들은 변의 길이가 정수가 아니므로, 한 변의 길이가 $t$인 정육각형 하나 당 $t-1$ 개씩 추가로 정육각형이 생긴다는 말이 되고, 이걸 다시 쓰면 결국 $H(n)$은 저 그림에서 찾을 수 있는 정수 길이 정육각형들의 한 변의 길이의 합으로 생각할 수 있다. ($t$짜리에 $t$배를 해 주어야 하니까, 이걸 변의 길이를 더하는걸로 생각하면 된다)

 

정수 길이 정육각형은 한 변의 길이가 1인게 $T_{n-2}$개, 2인 게 $T_{n - 5}$ 개, ... $k$인 정육각형이 $T_{n - 3k +1}$ 개 있으므로, 다음 식의 값이 그대로 답이 된다. (단, $T(n) = \frac{n(n+1)}{2}$

$$H(n) = \sum_{k = 1}^{\lfloor \frac{n}{3} \rfloor} k \ T_{n-3k+1}$$

 

코드 작성 때는 전부 2씩 밀어서, 그냥 $H(n-2)$ 를 계산하는 코드를 작성하고 1부터 12333까지 했다. 

import time
import Gratus_PE_Util as GPE
tn = []
def triangular_number(n):
	return n*(n+1)//2

def PE577_H(x):
	ans = 0
	for i in range(x//3+1):
		u = tn[x-3*i]
		u *= (i+1)
		ans += u
	return ans

def main():
	tn.append(0)
	for i in range(1,15000):
		tn.append(triangular_number(i))
	ans = 0
	for i in range(1,12344):
		ans += PE577_H(i)
	print(ans)

if __name__ == "__main__":
	start_time = time.time()
	main()
	print("--- %s seconds ---" % (time.time() - start_time))

Execution time : 7초. (맥북에서 돌린거라서, 데탑은 조금 더 빠르긴 할거 같다)