백준 8974번 [희주의 수학시험](C++) -yes6686- 티스토리

백준 문제 풀이: 8974번 [희주의 수학시험]

---

문제 링크: https://www.acmicpc.net/problem/8974

문제 설명:

1부터 시작하여 숫자 N이 N번 반복되는 수열을 만들고, 주어진 두 인덱스 범위 내에 있는 숫자의 합을 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[1001]; // 수열 저장 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int cnt = 0;
    int n = 1;
    
    // 수열 생성
    while (cnt < 1000) {
        for (int i = 0; i < n; i++) {
            arr[cnt] = n;
            cnt++;
            if (cnt >= 1000) break; // 1000개의 숫자 생성 후 종료
        }
        n++;
    }

    int a, b;
    cin >> a >> b; // 범위 입력
    int ans = 0;

    // 구간 합 계산
    for (int i = a - 1; i < b; i++) {
        ans += arr[i];
    }

    cout << ans; // 결과 출력
}

---

코드 설명

위 코드는 수열을 생성한 후, 주어진 구간에 해당하는 숫자들의 합을 계산합니다. 주요 로직은 다음과 같습니다:

1. 수열 생성: 숫자 N이 N번 반복되는 수열을 배열에 저장하며, 최대 1000개의 숫자까지 생성합니다.
2. 구간 합 계산: 배열의 A-1부터 B-1까지의 숫자를 합산하여 결과를 출력합니다.

시간 복잡도:

• 수열 생성: O(1000)
• 구간 합 계산: O(B - A)

전체 복잡도는 수열 생성과 구간 합 계산을 포함하여 O(1000)입니다.

---

결과

위 코드를 통해 주어진 범위의 숫자 합을 정확히 계산할 수 있습니다. 추가적인 최적화는 필요하지 않지만, 더 간결한 구현 방식을 제안하고 싶다면 댓글로 공유 부탁드립니다!