39. Integer right triangles

1. 개요

  문제는 이곳에서 확인할 수 있다. 어떤 직사각형의 둘레의 길이가 \(p\)이며 각 변의 길이를 \(a, b, c\)라고 하자. 단, 모든 길이는 정수이며 \(a<b<c\)이다. \(p=120\)일 때 \( \left\{ a, b, c \right\} \)의 쌍은 {20,48,52}, {24,45,51}, {30,40,50}로 3개이다. \( \left\{ a, b, c \right\} \)의 쌍을 가장 많이 생성하는 \(p\)의 값을 구하는 것이 목표이다.

2. 구현

  \(p\)와 \(a\), \(b\), \(c\)의 관계로부터 \(2ab=p(p-2c)\)의 식을 유도할 수 있다, 이는 \(p\)는 반드시 짝수여야 한다는 것을 의미한다. 이를 이용하여 구현한다.

# -*- coding: utf-8 -*-

answer = {'p': 0, 'count': 0}

for p in range(12, 1001, 2):
    count = 0

    for a in range(1, int(p/3)):
        for b in range(a+1, int((p-a)/2)):
            c = p - a - b

            if c**2 == a**2 + b**2:
                count += 1

    if answer['count'] < count:
        print('SOLUTIONS FOR {p}: {count}'.format(p=p, count=count))
        answer.update({'p': p, 'count': count})

print('\nANSWER: {count} for {p}'.format(count=answer['count'], p=answer['p']))

답은 840으로 8개의 \( \left\{ a, b, c \right\} \)를 갖는다.