[백준][C++] 1059: 수2

문제 링크: https://www.acmicpc.net/problem/1059

 

문제 설명이 좀 헷갈릴 수 있습니다. Lucky? Unlucky? Set? 구간?... 혼란스럽습니다.

 

푸는방법은 이분탐색인데 이런식으로 Lucky set의 원소 a_i와 a_i+1 사이에 N이 있다고 해봅시다. 이때 N이 L 또는 R과 같으면 답이 없으니 0입니다.

 

N을 포함한 연속된 범위를 만들려면 어떻게 해야 할까요. 빨간색 범위 [L+1, N] 뒤에서부터 0, 1, ..., N-L-1개를 고르고, 초록색 범위 [N, R-1] 앞에서부터 0, 1, ..., R-N-1개를 고르면 됩니다. 둘은 독립이므로 전체 경우의 수는 (R-N)*(N-L), 이때 둘 다 0개를 선택하면 [N, N]으로 이건 안되니까 1을 빼주면 답은 (R-N)*(N-L)-1이 됩니다.

예외가 있는데, Lucky Set의 최솟값이 N보다 큰 경우 위 그림에서 L=0인 경우라 생각하면 됩니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int L;
	cin >> L;
	set<int> s;
	for (int i = 0; i < L; ++i) {
		int in;
		cin >> in;
		s.insert(in);
	}

	int N;
	cin >> N;

	if (*s.lower_bound(N) == N) {
		cout << 0 << '\n';
		return 0;
	}

	auto left = s.lower_bound(N);
	auto right = s.upper_bound(N);

	if (left != s.begin()) {
		left = prev(s.lower_bound(N));
		cout << (*right - N) * (N - *left) - 1 << '\n';
	}
	else
		cout << (*right - N) * N - 1 << '\n';
	
	return 0;
}