[JS] N까지의 수의 합

 

다시 코딩테스트 공부를 시작하면서, N까지의 수를 합을 구하는 공식이 있다는 것이 생각났다. 검색하면 많은 좋은 글이 나오는 내용이지만, 내 머릿속에 남기기 위해서 블로깅을 하기로 결정했다.

 

1 ~ N 까지의 합을 구하는 공식 = N(N + 1) / 2

// 1 ~ N까지 합을 구하는 공식
N * (N + 1)/2

공식은 정말 간단하다. 그렇다면 왜 이렇게 풀이가 되는 것일까?

삼각형을 생각하기

 

1부터 4까지의 합을 구해야한다고 가정한다. 이 문제를 그림으로 그리면 왼쪽과 같이 표현할 수 있다. 검정 원들을 보면 검정 원의 모음이 삼각형을 그리게 되는 것을 알 수 있다.

삼각형의 넓이를 구하는 공식을 기억해보자. 

삼각형의 넓이 = 높이 x 밑변 / 2

따라서 1 ~ N까지의 합이 N(N + 1) / 2가 되는 것이다.

 

 

 

 

 

 

N ~ M 까지의 합을 구하는 공식 = (N + M) *(M - N + 1) / 2

// N ~ M 까지의 합을 구하는 공식 = 사다리꼴의 넓이
(N + M) *(M - N + 1) / 2

사다리꼴을 생각하기!

3 ~ 5까지의 합을 구해야한다고 가정하면, 왼쪽과 같은 사다리꼴 모양이 그려진다.

즉, 사다리꼴의 넓이를 구하면 된다.

사다리 꼴의 넓이를 구하는 공식은 다음과 같다.

사다리꼴의 넓이 = (윗변 + 밑변) * 높이 / 2

우리는 여기서 윗변이 N, 밑변이 M이라는 것을 알 수 있다. 그렇다면 높이는 어떻게 알 수 있을까?

 

3 ~ 5까지 순차적으로 1씩 증가하는 경우, 높이를 구하는 방식은 아주 쉽다. M(밑변)에서 N(윗변)을 뺀 후 1을 더해주면 된다.

 

 

 

 

번외) 만약 N개씩 증가하는 수의 합을 구해야한다면?

N개씩 증가하는 숫자의 합도, 사다리꼴을 구하는 합과 다르지 않다. 다만 높이를 구하는 방법이 조금 다를 뿐이다.

2 씩 증가하는 수열을 2 ~ 6까지 더해야하는 문제이다. 왼쪽 이미지를 보면 알 수 있듯이 똑같이 사다리 꼴의 넓이를 구하면 된다.

이때 사다리꼴의 높이를 구하는 방법이 조금 다르다.

윗변을 N(2), 밑변을 M(6), 그리고 증가하는 숫자를 A(2)라고 부르겠다.

// 높이를 구하는 방법
(N + A * 높이) = M 
(A * 높이) = M - N
높이 = (M - N) / A
// 단, 여기서 시작값인 N이 들어가있지 않기 때문에 + 1을 해줘야한다.
따라서 높이 = (M - N) / A + 1

 

 

 

정리

이해가 되지않는다면, 직접 하나하나 그려보는 것을 추천한다. 특히 아래 참고 사이트는 더 자세히 설명이 나와있으니 읽어보길!

---

참고 사이트

https://adgw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-1-n%EA%B9%8C%EC%A7%80-%ED%95%A9%EC%9D%84-%EA%B5%AC%ED%95%98%EB%8A%94-%EC%9B%90%EB%A6%AC

[알고리즘] 1 ~ n까지 합을 구하는 원리