문제링크: 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을 포함하는 좋은 구간의 개수를 출력한다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
	std::ios::sync_with_stdio(false);
	std::cout.tie(NULL);
	std::cin.tie(NULL);
	
	int L; std::cin >> L;
	std::vector<int> v(L);
	bool issame = false;

	for (int i = 0; i < L; i++) {
		std::cin >> v[i];
	}

	std::sort(v.begin(), v.end());

	int n; std::cin >> n;

	for (int i = 0; i < L; i++) {
		if (v[i] == n) {
			issame = true;
			break;
		}
	}

	if (issame) {
		std::cout << 0 << "\n";
	}
	else {
		int start = 0;
		int end = 0;

		for (int i = 0; i < L; i++) {
			if (v[i] > n) {
				start = v[i - 1];
				end = v[i];
				break;
			}
		}

		int ans = 0;

		for (int i = start + 1; i < end; i++) {
			for (int j = i + 1; j < end; j++) {
				// std::cout << i << " " << j << "\n";
				if (i <= n && n <= j) {
					ans++;
				}
			}
		}

		std::cout << ans << "\n";
	}

	return 0;
}

이 문제는 생각만 잘 하면 단순하다.
우선 벡터에 넣고 sorting을 해준다.
그 후 n 사이의 구간을 정한다.
start와 end의 값을 loop로 돌려서 사이에 n이 포함될 때마다 ans를 증가시켜준다.

노트

문제에서 찾는 범위를 정확하고, 가능한 좁은 범위로 추려내야한다.
만약 start와 end값을 정하지 않고 L 크기만큼의 loop를 돌렸으면 괴랄하고 무식한 방법이 되었을 것이다.