[백준 1059] 좋은 구간 (C++)

https://www.acmicpc.net/problem/1059

문제

---

정수 집합 S가 주어졌을때, 다음 조건을 만족하는 구간 [A, B]를 좋은 구간이라고 한다.

• A와 B는 양의 정수이고, A < B를 만족한다.
• A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다.

집합 S와 n이 주어졌을 때, n을 포함하는 좋은 구간의 개수를 구해보자.

 

입력

---

첫째 줄에 집합 S의 크기 L이 주어진다. 둘째 줄에는 집합에 포함된 정수가 주어진다. 셋째 줄에는 n이 주어진다.

 

출력

---

첫째 줄에 n을 포함하는 좋은 구간의 개수를 출력한다.

 

제한

---

• 1 ≤ L ≤ 50
• 집합 S에는 중복되는 정수가 없다.
• 집합 S에 포함된 모든 정수는 1보다 크거나 같고, 1,000보다 작거나 같다.
• 1 ≤ n ≤ (집합 S에서 가장 큰 정수)

문제 풀이

---

수학 문제.

 

문제의 조건에 따라 n이 집합 S에 포함된 정수라면 좋은 구간이 존재하지 않으므로 0을 출력하면 된다. 집합 S에 포함되지 않은 정수라면 좋은 구간은 [n보다 작은 수, n과 같거나 큰 수]가 된다. 이 모든 수는 집합 S에 존재하지 않아야 하므로, 경계가 되는 값은 집합 S에 존재하는 n보다 작으면서 가장 큰 수에 1을 더한 것(이를 i라 하자)과, 집합 S에 존재하는 n보다 크면서 가장 작은 수에 1을 뺀 것(이를 j라 하자)이다.

이를 바탕으로 A가 i일 때부터 j일 때까지 가능한 경우의 수를 구해준다. A가 n이 되면 더 이상 좋은 구간이 존재하지 않으므로 break를 걸어주면 된다.

n이 집합 S에 존재하는 가장 작은 수보다 작은 경우가 있다. 이때는 1부터 집합 S에 존재하는 가장 작은 수 - 1를 대상으로 좋은 구간을 찾아주면 된다.

 

아래는 코드.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

	int L, num, N;
	vector<int> v;
	long long answer = 0;
	cin >> L;
	for (int i = 0; i < L; i++)
	{
		cin >> num;
		v.push_back(num);
	}
	sort(v.begin(), v.end());
	cin >> N;
	if (find(v.begin(), v.end(), N) != v.end())
	{
		cout << 0 << "\n";
	}
	else
	{
		int min, max;
		int maxIndex = lower_bound(v.begin(), v.end(), N) - v.begin() ;
		int minIndex = maxIndex - 1;
		if (minIndex == -1)
		{
			min = 1;
		}
		else
		{
			min = v.at(minIndex) + 1;
		}
		max = v.at(maxIndex) - 1;
		for (int i = min; i <= max; i++)
		{
			answer += v.at(maxIndex) - i - (N - i);
			if (i == N)
			{
				answer--;
				break;
			}
		}
		cout << answer << "\n";
	}
	return 0;
}