C++ 코딩테스트 강좌, 숫자의 합 구하기

문제 정의

주어진 자연수 N에 대해, 1부터 N까지의 정수의 합을 구하는 프로그램을 작성하시오.

예를 들어, N이 5일 경우, 1 + 2 + 3 + 4 + 5의 결과인 15가 출력되어야 합니다.

입력 및 출력

입력

단일 정수 N (1 ≤ N ≤ 100,000)이 주어집니다.

출력

N까지의 정수의 합을 한 줄에 출력합니다.

문제 풀이 과정

1단계: 알고리즘 이해하기

숫자의 합을 구하기 위해서는 기본적으로 반복문을 사용할 수 있습니다. 주어진 자연수 N까지 반복하면서 각 숫자를 더하는 방식입니다. 그러나 수학적인 공식을 활용하면 더 효율적으로 풀 수 있습니다.

2단계: 수학적 접근

1부터 N까지의 합을 구하는 공식은 다음과 같습니다:

Sum = N * (N + 1) / 2

이 공식을 사용하면 O(1) 시간 복잡도로 문제를 해결할 수 있습니다. 공간 복잡도 또한 O(1)로 유지됩니다.

3단계: C++ 코드 구현

이제 구현 단계로 넘어가겠습니다. 아래는 해당 문제를 해결하기 위한 C++ 코드입니다.

#include <iostream>
using namespace std;

int main() {
    int N;
    cout << "N의 값을 입력하세요: ";
    cin >> N;

    // 공식을 이용한 합 계산
    long long sum = static_cast(N) * (N + 1) / 2;
    
    cout << "1부터 " << N << "까지의 정수의 합은: " << sum << "입니다." << endl;

    return 0;
}

        

4단계: 예제 입력 및 출력

주의 깊게 코드를 확인 한 후, 몇 가지 예시를 통해 결과가 올바른지 확인해 봅시다.

예제 1:

입력: 5

출력: 1부터 5까지의 정수의 합은: 15입니다.

예제 2:

입력: 10

출력: 1부터 10까지의 정수의 합은: 55입니다.

예제 3:

입력: 100

출력: 1부터 100까지의 정수의 합은: 5050입니다.

최적화 방안

이 문제는 수학 공식을 사용하여 O(1)로 해결하였기 때문에 별도의 최적화가 필요하지 않습니다. 그러나 입력 데이터의 범위가 줄어들 경우, 반복문을 사용하여 합을 구하는 방법은 비효율적일 수 있습니다.

예를 들어, N이 매우 큰 경우 반복문을 사용할 경우 시간이 오래 걸릴 수 있으며, 이로 인해 시간 초과 오류가 발생할 수 있습니다. 수학 공식은 이러한 문제를 해결하는 데 특히 유용합니다.

예상 질문과 답변

Q1: 만약 N이 음수일 경우에는 어떻게 되나요?

A1: 본 문제의 조건에서는 N이 1 이상의 자연수로 제한되어 있으므로 음수 입력이 주어지지 않습니다. 입력 범위를 철저히 체크하는 것이 좋습니다.

Q2: C++ 외 다른 언어에서도 구현 가능한가요?

A2: 네, 숫자의 합을 구하는 알고리즘은 다른 프로그래밍 언어에서도 동일하게 적용할 수 있습니다. 단, 각 언어의 문법에 맞게 코드를 수정해야 합니다.

Q3: 이 문제의 변형 버전은 없나요?

A3: 이 문제는 기본적인 숫자 합 문제입니다. 변형을 원하신다면, 예를 들어 짝수나 홀수만 더하는 문제를 제시해 볼 수 있습니다.