오각수는 Pn = n (3n − 1)/2 라는 공식으로 구할 수 있고, 처음 10개의 오각수는 다음과 같습니다.
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
위에서 P4 + P7 = 22 + 70 = 92 = P8이 됨을 볼 수 있습니다. 하지만 두 값의 차인 70 − 22 = 48 은 오각수가 아닙니다.
합과 차도 모두 오각수인 두 오각수 Pj, Pk 에 대해서, 그 차이 D = | Pk − Pj | 는 가장 작을 때 얼마입니까?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | list =[] result = [] for n in range(1, 3000): list.append((n*(3*n-1))/2) cnt = 0 for n1 in list: cnt +=1 for n2 in list[cnt:]: if list.count(n1 + n2): if list.count(n2 - n1): print n2, n1, "n2 - n1 :", n2-n1, '-------------------' result.append(n2-n1) print result | cs |
처음 문제를 봤을 때 2개의 루프를 만들기 싫어서 한 루프 안에서 처리할 궁리를 했지만 p4 + p7이 p7을 넘어가는 부분 때문에 오각수를 담는 리스트를 만들었습니다.
count로 해당 수가 오각수이면 1을 반환할 것이고 숫자가 커질수록 n2-n1이 커지기 때문에 임의로 정한 범위를 초과하는 테스트는 필요없습니다. 여러개의 오각수가 나온다면 그 중 가장 작은 수를 고르면 될 것이라 생각했습니다.
7042750 1560090 n2 - n1 : 5482660 -------------------
[5482660]
'* Computer Science > Project Euler' 카테고리의 다른 글
| project euler 52. problem (0) | 2016.11.14 |
|---|---|
| project euler 41.problem (0) | 2016.10.20 |
| project euler 37. problem (0) | 2016.10.13 |
| project euler 43. problem (0) | 2016.10.05 |
| Permutation (0) | 2016.09.30 |