문제

동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다.

이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다.

하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자.

  • 입력
    • 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다.
  • 출력
    • 첫 줄에 구간에 속하는 숫자의 합을 출력한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>
using namespace std;

pair<int, int> checkNum(int n){
    int num = 1;
    int sum = 0;
    while(true){
        sum += num;
        if (sum >= n) return make_pair(num, sum - num);
        else num++;
    }
}

int checkSum(pair<int, int> v, int sum, int n){
    for (int i = 1; i <= v.first; i++){
        if (i == v.first) sum += (n - v.second) * i;
        else sum += i * i;
    }

    return sum;
}

int main(void){
    int a, b;

    cin >> a >> b;

    pair<int, int> v1 = checkNum(a - 1);
    pair<int, int> v2 = checkNum(b);

    int a_sum = 0, b_sum = 0;

    a_sum = checkSum(v1, a_sum, a - 1); 
    b_sum = checkSum(v2, b_sum, b);

    int total = b_sum - a_sum;

    cout << total << endl;

    return 0;
}

접근 및 풀이

안 쉽게 푸는 문제
최근에 풀었던 문제 중에서 그마나 고민을 좀 깊게 했던 문제이다. 딱 보고 어떻게 풀어야 할지 감이 안 잡혀서 이런저런 풀이들을 찾아봤는데 너무 하드코딩식으로 푼 방법이 많아서 풀 방법을 열심히 고민해보았다.

일단 대부분의 사람들이 푼 방법은 범위가 1000으로 한정되어 있으니 1000개짜리 배열을 만들어서 숫자를 일일히 집어 넣은 다음 직접 구한다… 는 하드코딩 식 방법이었는데 개인적으로 PS 풀 때 그 문제에만 대입되는 하드코딩식 방법을 굉장히 싫어하기 때문에 나름 합리적인 다른 방법을 생각해 보기로 했다.

image

대략적으로 내가 문제를 푼 방법을 그림으로 나타내면 위와 같다고 할 수 있다. 3번째부터 7번째까지의 수의 합을 구하려면 7번째까지의 모든 수의 합에서 3번째의 앞인 2번째까지 모든 수의 합을 빼면 구할 수 있다.

그럼 합은 어떻게 구할 것이냐?

이걸 생각하는 게 이 문제의 관건이었다. 몇 번째의 수열은 무슨 숫자인지, 그 숫자들 중에서도 몇 번째인지를 구하면 바로 합을 구할 수 있기 때문에 굳이 1000번째로 한정해놓지 않아도 문제를 풀 수 있게 된다.

나는 checkNum 함수에서 해당 순서의 수열이 무슨 숫자일지, 또 몇 번째일지 구할 수 있도록 하였다. 수열의 숫자는 1부터 시작하고, 1씩 커지면서 개수 또한 해당 숫자만큼 늘어나기 때문에 1부터 2, 3.. n + 1까지 더하게 되면 수열의 숫자와 다음 숫자로 넘어가는 마지막 기점의 순서를 알 수 있게 된다. 예를 들자면 처음 숫자 1 다음 숫자 2는 두번 나오기 때문에 마지막 2는 세번 째에 나오게 된다. checkNum에서는 순서를 변수로 넣고, 숫자를 계속 더하면서 순서 sum이 해당 순서보다 커지거나 같아지면 해당 순서의 숫자인 num과 앞 숫자가 몇 번째에 끝났는지를 return 한다.

다음 checkNum에서 구한 두 개의 리턴 값 (해당 순서의 숫자, 그 앞 숫자가 끝난 순서)를 이용해 checkSum 함수에서 그 앞 숫자가 끝난 순서까지는 i*i를 이용해 합을 구해주고, (현재 구할 순서 - 그 앞 숫자가 끝난 순서) * 해당 순서의 숫자를 이용해 나머지 합을 구해준다.

정리하자면

  1. a와 b를 입력받는다.
  2. checkNum을 이용해 a-1번째 숫자 n과 n-1이 몇번째에서 끝났는지 / b번째 숫자 m과 m-1이 몇 번째에서 끝났는지 구한다.
  3. checkSum을 이용해 a-1번째까지의 모든 숫자의 합 / b번째까지의 모든 숫자의 합을 구한다.
  4. b번째까지의 숫자의 합 - a-1번째까지의 모든 숫자의 합을 구하면 a와 b 구간 사이 숫자들의 합을 구할 수 있다.

라고 할 수 있겠다.

좀 더 복잡하지만 효율적인지는 모르겠다. 시간이나 메모리를 따지면 그냥 배열에 때려넣는게 맞기는 한데 해당 구간보다 조금 더 클 때, 또 범용적인 상황을 생각하면 이게 맞는거 같기도…

댓글남기기