프로젝트 오일러 28번 - 대각선수의 합

자연수를 1부터 25까지 아래와 같이 배열하고, 대각선상의(빨간색) 숫자의 합을 구하면, 101입니다.

21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13

문제는, 위 사격형의 크기를 1001 x 1001 만들었을때 대각선의 모든수의 합을 구하는 것입니다.

일단, 규칙을 찾아보면, 우측상단 수가 완전제곱수로 증가하는 것을 볼수 있습니다. 이걸 이용해서, 1001x1001 까지계산해 볼 수 있겠네요.

1. 먼저 완전제곱수 루프를 만들겠습니다.(일단 9x9 사각형까지만,n=9)

n=9
for i in range(1,n+1,2):
    print(i, pow(i,2))

2. 매 루프마다 나머지 세꼭지점을 찾고,

n=9
for i in range(1,n+1,2):
    print(i, pow(i,2))
    print("diaginal number:",pow(i,2)-i+1,pow(i,2)-i*2+2,pow(i,2)-i*3+3)

1 1
diaginal number: 1 1 1
3 9
diaginal number: 7 5 3
5 25
diaginal number: 21 17 13
7 49
diaginal number: 43 37 31
9 81
diaginal number: 73 65 57

3. 합산합니다.

n=9;total=0
for i in range(1,n+1,2):
    value=pow(i,2)
    print("dimension:",i, "value:",value)
    if i>1:
        print("diaginal number:",value-(i-1),value-(i-1)*2,value-(i-1)*3)
        total=total+value*4-(i-1)*6
        print(total)
    else:
        total+=i

dimension: 1 value: 1
dimension: 3 value: 9
diaginal number: 7 5 3
25
dimension: 5 value: 25
diaginal number: 21 17 13
101
dimension: 7 value: 49
diaginal number: 43 37 31
261
dimension: 9 value: 81
diaginal number: 73 65 57
537

중간에 if 문은 n=1일때는 계산이 예외이기 때문에, 그걸 처리하기 위해서 넣어줬습니다.

4. 마지막 1001x1001까지 계산.

n=1001;total=0
for i in range(1,n+1,2):
    value=pow(i,2)
    if i>1:
        total=total+value*4-(i-1)*6
    else:
        total+=i
print(total)

669171001

프로젝트 오일러 28번 - 대각선수의 합

댓글