[프로그래머스] 부족한 금액 계산하기 - 가우스 덧셈

갸아악 프로그래머스는 코딩테스트할 때만 써보고 공부하기 위해 써보는건 처음이다. 오늘부터 1일 1문제이상+1알고리즘 정리에 도전합니다

부족한 금액 계산하기

해당 문제의 포인트는 price와 count를 입력 받았을 때,
price는 count 횟수만큼 더 해지는데 더해질 때마다 배수가 되어 더해진다.

price 100 
count 4

(100*1)+(100*2)+(100*3)+(100*4)

나는 for문을 이용해 풀었지만 가우스 덧셈을 사용해 깔끔하게 푼 것을 보고 충격...!

가우스 덧셈

1에서 n까지의 총합
n(n+1)/2

급식을 먹을 시절 배웠던 것 같은데 하나도 기억나지 않는다.
그냥 받아들이지 못하고 이해를 해야 받아 들여지는 피곤한 성격상 왜 이런 식이 나오는지 열심히 찾아보았다.

n이 10일 때

1에서 n까지 더할 때 끝과 끝의 합끼리 더하면 같은 합이 나온다. 

1+10
2+9
3+8
4+7
5+6

총 n/2만큼 수행한다. (5번)
모든 식의 합이 n+1이 나온다 (11)

(n+1) 최대값 n+최소값1
n(n+1)/2 n/2만큼 수행

이렇게 1에서 10까지의 합이 10(10+1)/2 = 55가 나오는 것을 알 수 있다. 하지만 부족한 금액 계산하기에서는 조건이 하나 더 있는데 바로 price가 배수가 되어 더해져야한다는 것! 가우스의 덧셈을 이용하면 매우 간단해 진다.

(price*n)(n+1)/2

price만 n에 곱해주면 for문 안쓰고 바로 해결된다!!!
학교 다닐 때 수학 좀 열심히 할걸...ㅠㅠ