[Baekjoon/C++] 1059번 - 좋은 구간

Baekjoon Online Judge

문제로 이동

 

문제

정수 집합 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에서 가장 큰 정수)

 

---

예제 입력	예제 출력
4 1 7 14 10 2	4
5 4 8 13 24 30 10	5
5 10 20 30 40 50 30	0
8 3 7 12 18 25 100 33 1000 59	1065

---

풀이

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

int main() {
	int L; // 집합 S의 크기 L
	int S[51]; // 집합에 포함된 정수
	int n; // 구간에 포함되어야 하는 정수

	// 입력
	cin >> L;
	for (int i = 0; i < L; i++)
		cin >> S[i];
	cin >> n;

	// 정렬
	sort(S, S + L);

	int idx = -2;

	// n보다 작은 정수 중에서 n과 가장 가까운 수의 위치 찾기
	for (int i = 0; i < L; i++) {
		// n이 집합 S에 속할 때
		if (S[i] == n) {
			idx = -1;
			break;
		}

		if (S[i] < n) idx = i;
	}

	int count = 0; // n을 포함하는 좋은 구간의 개수

	if (idx != -1) {
		int start = 1; // 구간에 포함될 수 있는 가장 작은 수
		int end = S[0] - 1; // 구간에 포함될 수 있는 가장 큰 수

		if (idx >= 0) {
			start = S[idx] + 1;
			end = S[idx + 1] - 1;
		}

		// n을 포함하는 좋은 구간의 개수 찾기
		for (int i = 0; ; i++) {
			if (start + i > n) break;

			count += (end - n + 1);
		}

		count--;
	}

	// 출력
	printf("%d\n", count);
	
	return 0;
}

 

	// 정렬
	sort(S, S + L);

	int idx = -2;

	// n보다 작은 정수 중에서 n과 가장 가까운 수의 위치 찾기
	for (int i = 0; i < L; i++) {
		// n이 집합 S에 속할 때
		if (S[i] == n) {
			idx = -1;
			break;
		}

		if (S[i] < n) idx = i;
	}

n을 포함하는 구간은 집합 S에서 n과 가장 가깝고 작은 숫자와 가장 가깝고 큰 숫자 사이에 존재한다. 그러므로 S를 오름차순으로 정렬하고, n과 가장 가깝고 작은 숫자가 저장된 인덱스를 찾았다. 만약 n이 집합 S에 속한다면 좋은 구간의 조건을 지킬 수 없기에 idx에 -1을 저장해서 이를 알린다. idx가 만약 -2라면 n은 1 ~ 0번째 인덱스의 숫자 사이에 위치한다는 것을 알리게 된다.

 

	int count = 0; // n을 포함하는 좋은 구간의 개수

	if (idx != -1) {
		int start = 1; // 구간에 포함될 수 있는 가장 작은 수
		int end = S[0] - 1; // 구간에 포함될 수 있는 가장 큰 수

		if (idx >= 0) {
			start = S[idx] + 1;
			end = S[idx + 1] - 1;
		}

만약 idx가 -1이라면 구간이 존재할 수 없는 것이기에 count는 0으로 유지되고, idx가 -1이 아니라면 if문 안의 코드가 실행된다. 구간에 포함될 수 있는 가장 작은 수와 가장 큰 수를 각각 start와 end에 입력하고 구간의 개수를 구했다.

 

		// n을 포함하는 좋은 구간의 개수 찾기
		for (int i = 0; ; i++) {
			if (start + i > n) break;

			count += (end - n + 1);
		}

		count--;

end - n + 1이라는 식은 아래의 과정의 통해 얻었다.

시작이 start + i인 구간의 수 = end - (start + i) - (n - 1 - (start + i))
				= end - (start + i) - (n - 1 - start - i)
				= end - start - i - (n - 1 - start - i)
				= end - start - i - n + 1 + start + i
				= end - n + 1

ex) 구간에 들어갈 수 있는 수가 2 ~ 6, n = 4

(2,4) (2,5) (2,6)	(6 - 4 + 1) = 3
(3,4) (3,5) (3,6)	(6 - 4 + 1) = 3
(4,4) (4,5) (4,6)	(6 - 4 + 1) = 3
(4,4)는 좋은 구간이 아니므로 -1

총 8개