문제
긴 철사를 구부려서 세 변이 정수인 직각 삼각형을 만들 때, 그 방법이 한 가지 뿐인 경우는 12cm를 최소로 해서 아래와 같이 여러 개가 있습니다.
12cm: (3, 4, 5)
24cm: (6, 8, 10)
30cm: (5, 12, 13)
36cm: (9, 12, 15)
40cm: (8. 15, 17)
48cm: (12, 16, 20)
반면에, 20cm의 경우 처럼 세 변이 정수인 직각 삼각형을 만들 수 없을 때도 있고, 여러 종류의 직각 삼각형을 만들 수 있을 때도 있습니다. 예를 들어 120cm의 철사로는 세 가지의 서로 다른 직각 삼각형이 만들어집니다.
120cm: (30, 40, 50), (20, 48, 52), (24, 45, 51)
그러면 길이가 백오십만(1,500,000)이하인 철사를 가지고 세 변이 정수인 직각삼각형을 만들 때, 그 길이로는 한가지 방법으로만 만들 수 있게 되는 경우는 모두 얼마나 됩니까?
접근
어찌보면 간단한 수 같아 보일 수도 있다. 키가 12~1,500,000 의 정수 수열인 사전을 준비하고, 합이 1,500,000 이하인 세 정수 a, b, c 에 대해서 피타고라스 정리를 만족하는지를 검사하고, 검사하면 사전에 그 세수의 합에 해당하는 값을 1만큼 추가한다. 모든 과정이 끝나고나면 사전에서 값이 1인 키 값만 검사해서 합산하면 된다.
문제는 이 전수조사의 양이 너무 많다는 것이다. 150만번만 돌면 되는 것도 아니고 각 길이 값 내에서 다시 a, b 값을 순차적으로 바꿔가면서 돌아야하니 인간적으로 계산해야하는 횟수가 너무 많다. 전수 조사라는 컨셉을 피해갈 수는 없으니 조사 대상을 극적으로 줄여서 성능을 끌어올릴 방법을 강구해야 한다.
원시 피타고라스 수
흔히 ‘피타고라스 수’라고 하는데, 정확히는 ‘피타고라스 트리플(삼조)’이다. 피타고라스 삼조는 피타고라스 정리를 만족하는 세 양수의 튜플이다. 이 때 세 수가 서로 소라면 이를 원시 피타고라스 삼조라 한다.
임의의 피타고라스 삼조에 대해 각 요소값을 n배 한 튜플 역시 피타고라스 삼조가 된다. 즉 만약 우리가 150만 미만의 원시피타고라스 삼조를 알고 있다면, 찾을 수 있는 모든 (a, b, c)의 조합은 이 원시피타고라스 삼조의 배수라는 뜻이다.
원시 피타고라스 삼조는 서로 소인 두 홀수가 있다면 다음과 같이 생성가능하다.
- m * n
- (m * m + n * n) / 2
- (m * m – n * n) / 2
이를 이용해서 다음과 같이 피타고라스 삼조를 생성하는 함수를 만들 수 있다. 두 수가 서로 소가 아니거나, 둘 중 하나 이상이 짝수라면 None을 리턴하도록 한다.
def make_ps(m, n):
m, n = (m, n) if m >= n else (n, m)
if m % 2 is 0 or n % 2 is 0 or\
gcd(m, n) > 1:
return None
a = m * n
b = (m*m - n*n) // 2
c = (m*m + n*n) // 2
# 리턴시에는 작은 값부터 크기대로 정렬
return (b, a, c)입력값의 범위 제한
위 함수를 이용했을 때 n이 1이라면 m이 모든 홀수인 경우에 원시피타고라스 삼조를 만들 수 있다. 먼저 둘레가 150만이 될 수 있는 m, n 에 대해서 그 한계값을 찾아보자.
LIMIT = 1_500_000
def get_max_range():
m = 3
while True:
s = make_ps(m, 1)
if s is not None and sum(s) > LIMIT:
return m
m += 2계산하기
이제 get_max_range()를 실행해서 얻게되는 한계값까지 m, n을 늘려가면서 피타고라스 삼조를 만든다. 여기서 주목할 것은 얻게되는 세 값의 합이다. 원시 피타고라스 삼조를 얻게되면 그 합으로부터 150만 이하의 값에 대해서 합의 정수배에 해당하는 둘레에는 한 가지 방법이 계속 추가된다. 이런식으로 리스트 하나에 각 인덱스에 해당하는 둘레값에서 만들 수 있는 직각삼각형의 개수를 계산해 나갈 수 있다.
참고로 원시피타고라스 삼조를 2중 리스트 축약으로 계산해되지만, 이렇게하면 쓸데없이 많은 루프를 돌게되므로(약 5초 가량 소요된다.) 2중 for 루프를 돌면서 한계값을 초과하는 시점에 중단하는 방식으로 루프의 수를 줄인다. 아래 코드로 계산했을 때 전체 수행시간은 대략 0.3~0.4초 가량.
def e075():
max_range = get_max_range()
# 원시 피타고라스 삼조 전체의 집합을 구한다.
ps = set()
for m in range(3, max_range, 2):
for n in range(1, m, 2):
p = make_ps(n, m)
if p is not None:
if sum(p) < LIMIT:
ps.add(p)
else:
break
# 직각삼각형을 만드는 경우의 수 세기
ways = [0] * (LIMIT + 1)
for p in ps:
s = sum(p)
for i in range(s, LIMIT, s):
ways[i] += 1
print(sum(1 for x in ways if x == 1))