[백준알고리즘] 1024번: 수열의 합 -C++

[백준알고리즘] 1024번: 수열의 합 -C++

1024번: 수열의 합 (acmicpc.net)

1024번: 수열의 합

10억 이하의 자연수 N과 100 이하의 자연수 L이 주어졌을 때, 수열의 합이 N이면서 길이가 100 이하인 수열을 찾는 문제다.

 

이번 문제의 경우 쉽게 접근할 수 있었으나, 예상치 못한 곳에서 오버플로우가 발생해서 골치아팠다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

문제에 대한 접근법은 실제 여러 수를 직접 해보면서 알아냈다.

 

먼저, 홀수는 \(l = 2\)로 모두 찾아지기 때문에 이 경우를 예를 들겠다.

\(n = 21, l = 2\)

\(p = \lfloor n/l \rfloor =10\)

→ 수열: \(\{10, 11\}\)

 

보다시피 \(n\)이 홀수이며 \(l=2\)일 때, \(p\)와 \(p+1\)로 이루어진 수열이 생기기 때문에 항상 만족한다는 것을 알 수 있다.

 

다음은, \(n\)이 짝수이며 \(l=3\)을 만족하는 경우를 보겠다.

\(n=18, l=3\)

\(p = \lfloor n/l \rfloor =6\)

→ 수열: \(\{5, 6, 7\}\)

 

여기서는 \(p-1\), \(p\), \(p+1\)로 이루어진 수열이 생기기 때문에 항상 만족한다는 것을 알 수 있었다.

 

다음은 \(l = 4\)인 경우를 보겠다.

\(n=14, l = 4\)

\(p = \lfloor n/l \rfloor =3\)

→ 수열: \(\{2, 3, 4, 5\}\)

 

여기서는 \(p-1\), \(p\), \(p+1\)에서 \(p+2\)까지 포함되게 되면서 만족하는 수열을 찾을 수 있다는 것을 알 수 있다.

 

마지막으로 \(l=5\)일 때와 \(l=7\)일 때를 살펴보겠다.

\(n=20, l = 5\)

\(p = \lfloor n/l \rfloor =4\)

→ 수열: \(\{2, 3, 4, 5, 6\}\)

 

\(n=28, l = 7\)

\(p = \lfloor n/l \rfloor = 4\)

→ 수열: \(\{1, 2, 3, 4, 5, 6, 7\}\)

 

처음에 나는 모듈로 값까지 고려해서 생각을 해봤는데, 그렇게 몫과 나머지의 연관을 찾다보니까 자연스럽게 수열의 규칙을 찾게 되었다.

 

결과만 적어보자면, 몫을 기준으로 오른쪽으로는 \(l/2\)만큼, 왼쪽으로는 \((l-1)/2\)만큼의 수가 수열에 추가되어야 한다는 것이다.

 

이렇게 되면 수열의 길이도 맞고, 각각의 \(l\)에 따른 적절한 수열이 생성되기 때문이다. 이렇게 생성된 수열의 합이 \(n\)이 되느냐 아니냐를 따지면 된다.

 

수열의 합을 구해주는 과정은 \([1, right]\)의 합에서 \([1, left)\)의 합을 빼줌으로써 \([left, right\)의 합을 구해주었다. 이때 사용한 것은 가우스의 등차수열의 합 공식을 사용했다. 

이 과정에서 \(right * (right+1)\) 값이 중간에 계산이 되는데, 이 과정에서 int로 처리하면서 버퍼오버플로우가 발생했고, 그래서 한참을 원인을 못 찾았다. 결국 질문 게시판을 통해 알려주신 분이 계셔서 문제를 해결할 수 있었다.

 

---

 

여하튼, 아래는 위의 방법대로 푼 코드다.

문제 로직자체는 쉬웠는데, 이상한 곳에서 오버플로우 때문에 고생했다.

#include <iostream>
#include <vector>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	solve();
}

bool isNotAnswer(const int n, const int l, std::vector<int>& answer)
{
	int p = n / l;
	int64_t right = p + (l / 2);
	int64_t left = p - ((l - 1) / 2);

	if (left < 0)
		return true;

	int64_t sum = (right * (right + 1) / 2) - (left * (left - 1) / 2);
	
	if (n != sum)
		return true;

	for (int i = left; i <= right; i++)
		answer.push_back(i);

	return false;
}

void solve(void)
{
	int n, l;
	std::cin >> n >> l;

	std::vector<int> answer;
	while (l <= 100 && isNotAnswer(n, l, answer))
		l++;

	if (answer.empty() || 100 < answer.size())
	{
		std::cout << -1;
		return;
	}

	for (auto a : answer)
		std::cout << a << " ";
}