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

www.acmicpc.net/problem/1059

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

------------------------------------------------------------------------------------------------------------------------

풀이

<C++>

#include <iostream>

using namespace std;

int main() {
	int L; cin >> L;
	int n;
	int scaleRight = 1001, scaleLeft = -1001;
	int arr[51];

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

	cin >> n;

	for (int i = 0; i < L; ++i) {
		if (arr[i] - n >= 0) {
			scaleRight = min(scaleRight, arr[i] - n);
		}
		else {
			scaleLeft = max(scaleLeft, arr[i] - n);
		}
	}

	if (scaleRight != 1001 && scaleLeft != -1001 && scaleRight != 0) {
		cout << abs(scaleRight * scaleLeft) - 1;
	}
	else if (scaleLeft == -1001 && scaleRight != 0) {
		cout << n * scaleRight - 1;
	}
	else if (scaleRight == 0){
		cout << 0;
	}

	return 0;
}

좋은구간자체를 구하는 것은 어렵지 않다. 입력받은 값중에서 n보다 큰 값중 가장 가까운 값과의 차이와 n보다 작은 값중 가장 가까운 값과의 차이를 곱한 값에서 1을 빼주면 좋은 구간의 개수를 쉽게 구할 수 있다. 하지만, L이 1일때를 간과하고 있어서 계속 20%에서 답이 틀렸었다. L이 1일때도 n과 가장 가까운 작은 수를 0으로 생각해야 한다. 이 점에 주의하도록 하자.

 

1. L을 입력받고, 수열을 입력받아 arr에 저장한다.

2. n을 입력받고 수열과 비교하여 n보다 큰수와의 차이 중 최소값, n보다 작은수와의 차이중 최대값을 각각 구한다.

3. 각 케이스별로 절댓값과 적절한 연산을 통해 값을 출력한다.