백준 1292번: 쉽게 푸는 문제 (C++)
문제
동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다.
이 문제는 다음과 같다. 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 풀 때 그 문제에만 대입되는 하드코딩식 방법을 굉장히 싫어하기 때문에 나름 합리적인 다른 방법을 생각해 보기로 했다.
대략적으로 내가 문제를 푼 방법을 그림으로 나타내면 위와 같다고 할 수 있다. 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
를 이용해 합을 구해주고, (현재 구할 순서 - 그 앞 숫자가 끝난 순서) * 해당 순서의 숫자를 이용해 나머지 합을 구해준다.
정리하자면
- a와 b를 입력받는다.
checkNum
을 이용해 a-1번째 숫자 n과 n-1이 몇번째에서 끝났는지 / b번째 숫자 m과 m-1이 몇 번째에서 끝났는지 구한다.checkSum
을 이용해 a-1번째까지의 모든 숫자의 합 / b번째까지의 모든 숫자의 합을 구한다.- b번째까지의 숫자의 합 - a-1번째까지의 모든 숫자의 합을 구하면 a와 b 구간 사이 숫자들의 합을 구할 수 있다.
라고 할 수 있겠다.
좀 더 복잡하지만 효율적인지는 모르겠다. 시간이나 메모리를 따지면 그냥 배열에 때려넣는게 맞기는 한데 해당 구간보다 조금 더 클 때, 또 범용적인 상황을 생각하면 이게 맞는거 같기도…
댓글남기기