[Algorithm] 특정 수 까지의 합 구하기 / 등차수열 (가우스 공식)

프로그래머스 문제

---

프로그래머스의 "부족한 금액 계산하기" 문제다. 아래 3개 파라미터를 받는다.

 

• price : 놀이기구의 이용료
• money : 고객이 가지고 있는 금액
• count : 고객이 해당 놀이기구를 이용한 횟수

 

놀이기구를 이용한 횟수가 늘어날 때마다 횟수 만큼의 이용료를 더 받는다. 놀이기구의 이용료 price 가 100원이라면 1번 이용할 땐 100원, 2번 이용할 땐 200원, 3번 이용할 땐 300원이 된다. 놀이기구를 count 번 탔을 때 money 금액에서 얼마나 모자라는지를 반환해야 된다. 금액이 모자라지 않으면 0을 반환한다.

 

반복문을 이용하면 아래처럼 쉽게 풀 수 있다.

function solution(price, money, count) {
  let sum = 0;
  for (let i = 1; i <= count; i += 1) {
    sum += price * i; // 3 + 6 + 9 + 12 = 30
  }

  return sum <= money ? 0 : sum - money; // 30 - 20 = 10
}

solution(3, 20, 4); // 10

 

아래는 가우스 공식을 이용해서 해결한 코드로 좋아요를 가장 많이 받았다. 

function solution(price, money, count) {
  const tmp = (price * count * (count + 1)) / 2 - money;
  return tmp > 0 ? tmp : 0;
}

 

등차수열 (가우스 공식)

---

1부터 100까지 수를 모두 더할 때 $1 + 100 = 101$, $2 + 99 = 101$, $3 + 98 = 101$.. 모두 101이 나온다. $50 + 51 = 101$ 까지 계속 반복해서 101을 50번 더하면 1~100까지 수의 합이 된다.

 

따라서 1~100까지 수의 합은 $101 * 50 = 5050$이 된다. 1씩 증가하는 수열은 아래처럼 공식화할 수 있다.

n = 마지막 수(1부터 1씩 증가하는 수열에선 가장 마지막 수가 항의 개수)
101(n + 1)을 50(n / 2)로 곱하면 1~100까지의 모든 합이 된다. 혹은...
101(n + 1)을 100(n)으로 곱한 뒤 2로 나누면 1~100까지의 모든 합이 된다. 
**(n + 1) * n / 2**

 

마지막 수(항의 개수)에서 2를 나누는 이유는? 항 개수 절반 지점을 넘을때부터 이미 더했던 수를 중복해서 더하기 때문이다.

47 + 54
48 + 53
49 + 52
50 + 51
------- 중간 지점
51 + 50
52 + 49
53 + 48
54 + 47
...

 

항의 개수 구하기

1부터 1씩 증가하는 수열에선 항상 마지막 수가 항의 개수가 된다.

 

1부터 100까지는 각 항이 1씩 증가하므로 총 항의 개수도 100이라는걸 바로 알 수 있다. 하지만 1, 3, 5, 7, 9 이렇게 2씩 증가하는 수열은 먼저 몇개의 항이 있는지부터 계산해야 한다. 아래 공식으로 쉽게 구할 수 있다.

((마지막 수 - 첫번째 수) / 수열의 증가폭) + 1

 

3, 5, 7, ...401 수열이 있다고 가정하면...

• 첫번째 항(3)부터 마지막 항(401)까지 $401 - 3 = 398$ 만큼 증가한다.
• 수열이 2씩 증가하므로 첫번째 항부터 마지막 항에 도달하기 까지 $398 / 2 = 199$ 개의 항이 있다.
• 첫번째 항도 포함해야 하므로 $199 + 1 = 200$ 개의 항이 있다.

 

위 공식대로 다른 수열의 항 개수도 구해보면...

• 1~100까지 1씩 증가하는 수열은 $((100 - 1) / 1) + 1 = 100$ 개의 항이 있다
• 1, 3, 5, 7, 9까지 2씩 증가하는 수열은 $((9 - 1)/2) + 1 = 5$ 개의 항이 있다

 

수열의 모든 합 구하기

모든 항의 개수를 구했으니 가우스가 초등학교때 풀었던 방식을 그대로 적용하면 된다.

(첫번째 수 + 마지막 수) * (항의 개수 / 2)

 

3, 5, 7, ...401 까지의 합을 구한다고 가정하면...

• 항의 개수 : $(401 - 3) / 2 + 1 = 200$
• 수열의 합 : $(3 + 401) * 200 / 2 = 40400$

 

문제에 등차수열 공식 적용하기

---

다시 프로그래머스 문제로 돌아와서 count만 따로 분리해서 생각해본다. count 파라미터를 4로 받았다면 1, 2, 3, 4 이렇게 1씩 증가하는 수열이 된다. 위에서 공부했던 등차수열 공식을 적용해서 count 숫자만큼의 총 합을 구해보면 $(4+1) * (4 / 2) = 10$이 된다.

 

첫번째 수는 항상 1이기 때문에 4(count) + 1을 했다. count는 1씩 증가하므로 항의 개수는 항상 count 수와 같아서 4/2를 했다. 코드로 풀어보면 아래와 같다.

(count + 1) * (count / 2);

 

여기에 price 값을 곱해주면 증가한 count까지 count * price 값을 모두 더한 금액이 된다. 

(count + 1) * (count / 2) * price;

 

고객이 원래 가지고 있던 돈 money를 빼주면 count번 만큼 놀이기구를 이용할 때의 초과금액을 구할 수 있다. 문제가 원하는 답이다.

(count + 1) * (count / 2) * price - money;

 

더 쉽게 생각해보기

좀 더 쉽게 생각해볼 수도 있다. price가 3, count가 4라고 가정했을 때, 아래처럼 price 숫자 만큼 증가하는 count개의 항을 갖는 수열이 된다.

3 + 6 + 9 + 12 = 30
(3 + 12) + (6 + 9) = 30

 

항의 개수는 항상 count 숫자와 같으므로 바로 모든 수열의 합을 구할 수 있다.

// (첫번째 수 + 마지막 수) * (항의 개수 / 2)
(price + price * count) * (count / 2);

 

레퍼런스

---

• 등차급수 (개념 이해하기) | 급수 | Khan Academy
• [김대수의 수학 어드벤처] 가우스는 어떻게 '1+2+ +99+100'을 순식간에 맞혔을까  

 

---

글 수정사항은 노션 페이지에 가장 빠르게 반영됩니다. 링크를 참고해 주세요