BOJ 1059 수2

www.acmicpc.net/problem/1059

1059번: 수2

일단 처음 봤을 때 문제 이해가 안된다..

질문게시판을 참고해서 이해했는데 lucky set이 주어지고 n이 주어지면 lucky set의 원소에서

n을 포함하고 있는 구간을 찾으면 된다.

 

무슨 소리냐면

1 7 4 10 

n = 2 라면

 

2를 포함하는 lucky set은 1과 7이고

2~6 사이의 구간 [2, 6]에서 2를 포함하는 구간을 따로 나눠서 세면 된다.

[2, 3], [2, 4], [2, 5], [2, 6] 이 있다. [3, ~] 은 2를 포함하지 않는다.

 

 [left + 1, n] ~ [n, right - 1]의 구간이기 때문에 (n - left) * (right - n)에서 가운뎃 값 1을 빼면 된다.

 

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

int ar[1001];

int main() {
	int n, l, min = 1001, max = 0;
	cin >> l;
	for (int i = 0; i < l; i++) cin >> ar[i];
	sort(ar, ar + l);

	cin >> n;

	for (auto i : ar) {
		if (i == n) {
			cout << 0 << endl;
			return 0;
		}
	}

	min = ar[lower_bound(ar, ar + l, n) - ar - 1];
	max = *upper_bound(ar, ar + l, n);
	cout << (n - min) * (max - n) - 1 << endl;

	return 0;
}

 

또한 lucky set에 n이 포함되어 있으면 구간 [a, b]가 존재하지 않기 때문에 0을 따로 출력해줘야 한다.

 

	min = ar[lower_bound(ar, ar + l, n) - ar - 1];
	max = *upper_bound(ar, ar + l, n);

 

lower_bound와 upper_bound를 활용해서 lucky set에 포함된 원소들을 쉽게 찾을 수 있었다.