https://www.acmicpc.net/problem/1292
문제
> 1을 한 번, 2를 두 번, 3을 세 번, 122333444455555 이런식으로 수열을 만든다.
> 수열에서 계산할 구간의 처음과 끝을 입력받는다.
> 예를들어 3 7을 입력받으면 세번째인 2부터 7번째인 4까지의 합을 구한다.접근
범위가 들어오면 각각의 1부터 해당 범위 -1 까지의 합을 구한다.
그리고 두 수열의 합을 빼주면 처음범위 부터 마지막 범위 -1 까지의 합을 구할 수 있다.
마지막 범위에 해당하는 수를 구해 더해주면 답을 구할 수 있다.
문제 해결
> 입렵받은 범위에 올 수있는 수의 개수는 n + (n+1) + (n+2)...에 + @개 이다.
따라서 이를 수식으로 변환해 반복문의 범위를 n * (n+1) / 2로 최소 개수를 구한 후 추가로 @개에 해당하는 수를 더해주었다.
> 해당 수열의 합은 인덱스를 1부터 시작하여 i^2으로 더해주었다.
> 부족한 범위의 수만큼 해당 인덱스에 올 수를 곱해 수열의 합에 추가로 더해주었다.
> 두 수열의 합을 뺐을때 겹치는 부분인 앞범위의 마지막 값을 뺴주었다.
ex)범위가 3, 7이면 1~3, 3~7의 합을 빼면 4~7의 결과가 나오기 때문에 1~3이 아닌 1~2까지를 구한 후 빼주었다.코드
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int arr[2];
cin >> arr[0] >> arr[1];
int max = 0;
int result[2] = { 0 };
for (int t = 0; t < 2; t++)
{
int sum = 0;
int i;
for (i = 1; (i * (i + 1)) / 2 <= arr[t]; i++)
{
sum += i * i;
max = i + 1;
if ((i * (i + 1)) / 2 == arr[t])
max = i;
}
result[t] = sum + (arr[t] - ((i * (i - 1)) / 2)) * max;
if (t == 0)
result[t] -= max;
}
cout << result[1] - result[0];
}
후기
수열의 범위와 합, 범위에 올 수 있는 수와 범위가 같을 때의 예외 등에 수식을 처리하는데 복잡함을 느꼈다. 압축할 수 있는 방법을 찾아봐야겠다.
