[C++]백준 - 1059번 문제

1059번: 좋은 구간 (acmicpc.net)

1059번: 좋은 구간

 

1059번 : 좋은 구간

---

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

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

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

 

입력

---

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

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

 

출력

---

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

 

 

 

---

 

생각해 볼 점

---

좋은 구간 구하는 방법

 

집합 S = {A, B}일 경우

 

1. 0 ~ A 사이  (따라서, N이 집합 S의 최소값보다 작으면 0~A 구간을 구해줘야 합니다.)

2. A ~ B 사이

 

* A ~ B 사이의 N을 포함한 좋은 구간 구하는 방법

 

좋은구간 [ S, E ]가 있다고 할 때

 

* A < S <= N

* N <= E < B

 

일 것이고, S의 갯수는 N - A, E의 갯수는 B - N이므로

 

(N - A) * (B - N)의 갯수만큼 좋은 구간이 있으며,

 

이 때, S = N, E = N인 구간은 없기 때문에 제거해주면

 

결국 (N - A) * (B - N) - 1만큼의 좋은 구간이 존재합니다.

 

코드

---

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

int main()
{
	int S, N;
	scanf("%d", &S);

	int* arr = new int[S + 1];
	for (int i = 0; i < S; i++) scanf("%d", &arr[i]);
	scanf("%d", &N);

	arr[S] = 0;
	int result = 0;

	sort(arr, arr + S + 1);
	for (int i = 0; i < S; i++)
	{
		int A = arr[i];
		int B = arr[i + 1];

		if (A < N && N < B)
		{
			result = (N - A) * (B - N) - 1;
			break;
		}
	}
	printf("%d", result);

	delete[] arr;
	return 0;
}

 

그 외

---