백준 8393 문제 풀이

https://www.acmicpc.net/problem/8393

---

문제

n이 주어졌을 때, 1부터 n까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n (1 ≤ n ≤ 10,000)이 주어진다.

출력

1부터 n까지 합을 출력한다.

---

해당 문제는 아주 유명한 일화를 바탕으로 나온 알고리즘 문제이다.

 

[ 1 ~ 100 까지의 모든 숫자의 합을 구하여라 ]

라는 문제를 몇초만에 풀었다는 학생의 일화가 유명하다.

 

풀네임을 잘 모를수 있으나 '가우스'는 많이들 들어 봤을 것이다.

(풀네임 : 카를 프리드리히 가우스)

 

위 가우스 일화를 기반으로 나온 계산식은 아래와 같다.

가우스의 등차수열의 합 계산 방식 :

    1,   2,   3,   4 ... 100

100, 99, 98, 97 ... 1

1 ~ 100 까지의 숫자와 반대로 100 ~ 1 까지의 숫자를 나란히 놓고 합을 해보면 어떻게 될까?

 

[ n + 1 ]

101, 101, 101, 101 ... 101 이 계산 된다.

( 1+100, 2+99, 3+99 ... 100 + 1 )

 

[ n ]

101 이라는 숫자의 개수는 1 ~ 100 의 숫자 수량이므로 100개이다. ( 즉, 101 * 100 = 10100 )

 

[ / 2 ]

1 ~ 100 과 100 ~ 1 숫자의 합 2개가 산출 되었으므로 나누기 2를 해준다. ( 즉, 10100 / 2 = 5050 )

 

위에서 나온 항목들을 계산 식으로 풀이한다면

( n + 1 ) * n / 2 와 같이 서술이 가능하다.

 

따라서 백준의 문제를 코드로 출력 한다면 아래와 같다.

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    cout << (n * (n + 1)) / 2 << endl;
    // (n * (n + 1)) 에서 바깥의 소괄호는 제거해도 무관하다.
    // 근데 보기 좋잖아
    return 0;
}