지나가던 개발자

[Algorithm] 1부터 n까지의 합이 {n(n+1)}/2인 이유 본문

Algorithm

[Algorithm] 1부터 n까지의 합이 {n(n+1)}/2인 이유

KwonYongHyeon 2022. 1. 17. 15:45

 저번에 백준의 8393번 문제를 풀며 이 공식에 관한 이야기를 잠시 했다.

 

 오늘 그 이유를 증명해보고자 한다.

 

 시작하기 앞서, 이 공식은 고등학교 수학I의 수열 단원에 나오며, 그 이름도 유명한 가우스가 사용했던 공식이라고 한다.

 

 우선 공차가 1인 등차수열 A가 있다고 생각해보자. 첫째항이 a, 공차가 d인 등차수열의 일반항은 An = a + (n - 1)d 이므로, An = n 이다.

 

 그렇다면 1부터 n까지의 이 수열은 {1, 2, 3, 4, 5, 6, 7, 8, ... , n-3, n-2, n-1, n} 이 될 것이다. 그렇다면 1부터 n까지의 합을 구하려면, 1부터 n까지 직접 더하는 방법이 있다. 그렇지만 이 방법은 너무나 비효율적이다.

 

s = 0
n = int(input())
for i in range(1, n+1):
    s += i
print(s)

 

 이런식으로 더할 수 있다고는 하지만, 만약 10,000,000,000,000정도 되는 큰 숫자가 나온다면 컴퓨터라 하더라도 연산에 오랜 시간이 걸릴 것이다.

 

 그렇다면 이런 방법을 써 보자.

 

 1에서 n까지의 수열을 한번 뒤집어보자. 뒤집은 뒤에 더해도 어처피 합은 똑같으니. 뒤집으면 {n, n-1, n-2, n-3, ... , 3, 2, 1}과 같은 수열이 나올 것이다.

 

 그러면 원래 있던 수열과 뒤집은 수열을 한번 더해보자.

 

 {1, 2, 3, ... , n-2, n-1, n}

 +

 {n, n-1, n-2, ... , 3, 2, 1}

 n+1, n+1, n+1, n+1, ... 

 

 놀랍게도 n+1만 계속 반복된다. 계속이 아니라 n번 반복된다. 그런데 n+1을 n번 더한다면 (1부터 n까지의 합)*2의 값이 될 것이다. 당연하게도 수열 두개를 더했으니. 따라서 {n(n+1)}/2으로 해줘야 한다. 이렇게 되니 우리가 맨 처음 증명하려 했던 식이 나왔다. 

 

 그렇다면 이번에는 공차가 2인 수열로 한번 해보자.

 

 {2, 4, 6, ... , n-4, n-2, n}

 +

 {n, n-2, n-4, ... , 6, 4, 2}

 n+2, n+2, n+2, n+2 ...

 

 이번에는 n+2만 계속 반복된다. 그렇게 되면 {n(n+2)}/2라는 식으로 계산하면 2부터 n까지 이어지는 공차가 2인 등차수열의 합을 구할 수 있겠다.

 

 그렇다면 이번에는 마지막으로, a를 첫째항, l을 제n항, 공차를 d로 갖는 수열 Sn으로 다시 한번 해보자.

 

 {a, (a+d), (a+2d), ... , (l-2d), (l-d), l}

 +

 {l, (l-d), (l-2d), ... , (a+2d), (a+d), a}

 a+l, a+l, a+l, a+l ...

 

 이번에는 a+l만 계속 반복된다. 그렇다면 a부터 l까지의 합은 {n(a+l)}/2로 나타낼 수 있을 것이다. 그런데 여기서 제n항 l은 a+(n-1)d 로 나타낼 수 있다. 첫째항 a에다가 공차 d를 n-1번 더한 것이라는 말이다. 왜 d를 n-1번 더하냐는 의문이 들 수도 있다. 그 이유는 a가 첫째항이기 때문이다. 제2항부터 n을 더하는데 a = S₁이니까, 결국 제n항 l은 a+(n-1)d가 되는 것이다.

 

 그렇다면 {n(a+l)}/2를 이렇게 나타낼 수 있겠다. n{a+a+(n-1)d}/2. 그럼 이걸 정리하면 n{2a+(n-1)d}/2가 된다.

 

 따라서, a를 첫째항, 공차를 d로 갖는 등차수열 Sn에서 a부터 l까지의 합은,

 n{2a+(n-1)d}/2

 이다.

 

 그렇다면 공차가 1, 첫째항이 1인 등차수열 An에서는

 n{2+(n-1)1}/2 = {n(n+1)}/2

 가 되는 것이다.

 

 그렇다면 이대로 코드를 한번 짜보고 원래 반복문을 사용했던 코드와 시간 복잡도를 비교하여 보자.

 

n = int(input())
print(n*(n+1)//2)

 

 1부터 1,000,000까지를 한번 더해 보았다.

 

 

 

 0.3초가 넘게 걸리던 코드를 0.00008초만에 해결할 수 있게 바꾸었다.