프로젝트 오일러 044

문제

44번 문제

합과 차도 모두 오각수인 두 오각수 차의 최솟값은?

사이냅소프트

오각수의 차이

이웃한 두 오각수의 차이는 3n + 1/2 입니다. 이웃한 두 오각수의 차는 오각수들이 커질수록 점점 커집니다. 순번의 거리가 k인 두 오각수의 차 역시, k와 n의 2차식으로 계산됩니다. 따라서 어떤 오각수의 차가 가장 작아지려면, n이 작은 것이 가장 유리하고, k가 작은 것이 그 다음으로 유리합니다.

왜 여기에 집중하는가 하면, 이 문제는 친화쌍을 찾는 앞선 프로젝트 오일러의 문제와 유사하지만, 오각수의 범위가 주어지지 않았다는 것입니다. 이 범위를 한정하는 것이 문제를 reasonable한 시간 내에 풀어내는 열쇠가 됩니다.

연속된 오각수가 있다고 가정합니다. 그 중 가장 큰 오각수 P(a)에서 바로 앞 오각수 P(a-1)을 뺍니다. 그 차이를 Q라 할 때, Q가 오각수라면 (연속된 오각수 목록에 있겠죠) Q와 P(a - 1)은 그 합이 오각수입니다. 그 차이가 오각수인지도 쉽게 알 수 있습니다. (P(a)보다 작은 오각수는 모두 있으니까요)

P(a)가 조건을 만족하지 않는다면, P(a - 1), P(a - 2), ... 이렇게 후보를 바꿔갑니다. 만약 만족하는 값을 찾지 못한다면 다시 P(a + 1)을 목록에 추가하고, 테스트를 반복합니다. 이 과정을 반복하는 중에 찾게되는 첫번째 값이 답이 됩니다.

def penta():
    k = 1
    while True:
        yield k * (3 * k - 1) // 2
        k += 1


def main():
    g = penta()
    ws = [next(g) for _ in range(10)]
    ps = set(ws)
    res, done = -1, False

    while not done:
        p = next(g)
        for s in ws[::-1]:
            t = p - s
            if t in ps and abs(t - s) in ps:
                res = abs(t - s)
                done = True
                break
        else:
            ws.append(p)
            ps.add(p)
    return res


if __name__ == '__main__':
    print(main())