BOJ 8974 - 희주의 수학시험

문제

BOJ 8974 - 희주의 수학시험

수열이 있다. 이 수열은 1이 1번, 2가 2번, 3이 3번, ..., k가 k번 나타나는 형식이다 (1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ...). 수열의 a번째부터 b번째 원소까지의 합을 구한다.

입력

두 정수 a, b가 한 줄에 공백으로 구분되어 주어진다 (1 이상).

3 8

출력

수열의 a번째부터 b번째 원소까지의 합을 출력한다.

18

예제

풀이

수열을 벡터에 미리 생성한 뒤 a번째부터 b번째까지 합산한다.

1. 1부터 1000까지 각 숫자 i를 i번씩 벡터에 추가하여 수열을 생성한다.
2. 인덱스 a-1부터 b-1까지 벡터 원소를 합산한다.
3. 합계를 출력한다.

핵심 아이디어: k번째 수까지 등장하는 총 원소 수는 k*(k+1)/2로 계산된다. 벡터를 미리 구성하면 임의 구간 합 계산이 간단해진다. 최대 1000*1001/2 = 500,500개 원소를 생성하므로 메모리와 시간 모두 허용 범위 내이다.

코드

#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
 
  int a, b;
  cin >> a >> b;
 
  vector<int> vec;
 
  for (int i = 1; i <= 1000; i++)
  {
    for (int j = 1; j <= i; j++)
    {
      vec.push_back(i);
    }
  }
 
  int sum = 0;
 
  for (int i = a - 1; i <= b - 1; i++)
  {
    sum += vec[i];
  }
 
  cout << sum;
  return 0;
}

복잡도

• 시간: O(K^2 + N) — K는 최대 숫자(1000), 수열 생성에 O(K^2/2), 구간 합 계산에 O(b-a+1) = O(N)
• 공간: O(K^2) — 수열 벡터 크기 최대 500,500