백준 1059. 좋은 구간

좋은 구간

수학 또는 브루트포스 문제

1. 간단 설명

---

다음 조건을 만족하면 “좋은 구간”이라고 한다

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

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

2. 예시

---

예제 1.

4
1 7 14 10
2

집합 S의 크기는 4, S = {1, 7, 14, 10}

2를 포함하는 좋은 구간의 개수는?

{2,3}, {2,4}, {2,5}, {2,6} 총 4개

예제 2.

3
10 20 30
5

문제의 제한 조건에서 1 ≤ n ≤ (집합 S에서 가장 큰 정수)로 주어졌다

즉, n이 S[0]보다 작은 경우, 1 <= n <= S[0]의 범위에 속한다

(A, B는 양의 정수이므로 1부터 가능)

위 케이스는 1<=5<=10 이므로

{1,5}, {2,5}, {3,5}, {4,5},
{1,6}, {2,6}, {3,6}, {4,6}, {5,6},
{1,7}, {2,7}, {3,7}, {4,7}, {5,7},
{1,8}, {2,8}, {3,8}, {4,8}, {5,8},
{1,9}, {2,9}, {3,9}, {4,9}, {5,9}

총 24개가 된다

3. 알고리즘

---

숫자가 속한 범위를 찾고,

그 범위 내에서 생성할 수 있는 구간을 찾고,

“종은 구간”의 개수를 찾는 방법 => 브루트 포스

그러나 수학적으로도 풀이가 가능함

시작 범위(A)와 끝 범위(B)를 찾았다면

좋은 구간의 개수는 = A를 선택하는 경우의 수 * B를 선택하는 경우의 수로 구할 수 있다

예를들어 S = {10, 20, 30, 40, 50}, n = 15 인 경우

A = 10, B = 20이고,

가능한 A : 11, 12, 13, 14, 15

가능한 B : 16, 17, 18, 19이다

생성 가능한 좋은 구간의 개수는 5 * 4 = 20이다

이런식으로 계산하면 간단히 정리 가능

1. L, S, N 입력받기
2. 오름차순으로 정렬
3. n이 S에 포함된 경우, 좋은 구간을 구할 수 없으므로, 0 출력 후 종료
4. low 값 찾기
	- n이 s[i]보다 작아지는 곳 까지 탐색 후 종료
5. high 값 찾기
	- s[i]가 n보다 커지는곳 까지 탐색 후 종료
6. 가능한 개수는 (low + 1부터 n까지) * (n부터 high - 1까지)
7. 출력

4. 소스코드

---

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

using namespace std;

int L, n;
vector<int> S;

void Input() {
	freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> L;
	S.resize(L);
	for (int i = 0; i < L; i++) {
		cin >> S[i];
	}

	cin >> n;
}

int main() {
	Input();

	sort(S.begin(), S.end());

	// n이 S에 포함되어 있는 경우
	if (find(S.begin(), S.end(), n) != S.end()) {
		cout << 0 << endl;
		return 0;
	}

	int low = 0;

	// low 값 찾기
	for (int i = 0; i < L; i++) {
		if (S[i] >= n) break;
		low = S[i];
	}

	// high 값 찾기
	int high = 1001;
	for (int i = 0; i < L; i++) {
		if (S[i] > n) {
			high = S[i];
			break;
		}
	}
	/*
	*
	가능한 시작점 (low + 1, n)
	가능한 끝점 (n, high -1)
	좋은 구간 개수 = A를 선택하는 경우의 수 x B를 선택하는 경우의 수
	= (n - low) * (high - n)
	
	*/
	int res = (n - low) * (high - n) - 1;
		
	cout << res;
}

1<= n <= S[0] 범위를 찾는게 생각보다 어려웠던 문제

또한 수학적으로도 간단히 풀 수 있는 방법이 떠오르지 않아 브루트포스로 풀었다가

다른 사람 풀이를 보고 이런 방법도 있다는 걸 배웠다