백준1059 - 수2

https://www.acmicpc.net/problem/1059

1059번: 수2

예제가 너무 빈약해서 푸는데 애먹은 문제다. 입력으로 lucky set이라는 집합이 주어지고 반드시 포함해야 될 수가 주어진다. 반드시 포함되어야 하는 수는 lucky set안에 있는 가장 큰 수보다 같거나 작다. 또한 구간이라는 정의가 주어지는데 [a, b]라고 정의가 되어있으면 "a이상 ~ b이하인 모든 자연수를 포함한다"라고 할 수 있다. b는 a보다 항상 크다. 이 구간은 0이상인 양의 정수로 정의된다. 

 

우리는 반드시 포함해야 되는 수를 가지고 있는 unlucky set을 만들어야 한다. unlucky set은 lucky set에 있는 수가 포함되어 있지 않은 수이다. 그리고 구간안에 반드시 포함되어야 하는 수가 있어야 한다.

 

주의할 점은 lucky set 외부에(lucky set의 최솟값) 반드시 포함되어야 하는 수가 주어진 경우다. 이점만 해결한다면 통과할 수 있을 것이다.

 

ex1.)

4

1 9 4 17

5

 

5를 반드시 포함해야 되고 구간은 5 ~ 8 사이다.

[5, 6], [5, 7], [5, 8] -> 3개

 

ex2.)

4

5 6 9 10

2

 

2를 반드시 포함해야 되고 구간은 lucky set 바깥인 1 ~ 3 사이다.

[1, 2], [1, 3], [1, 4], [2, 3], [2, 4] -> 5개

 

ex3.)

4

3 4 8 10

9

9를 반드시 포함해야 하지만 포함할 수 있는 구간이 없다. -> 0개

 

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

int main() {
	vector<int> v; //lucky set
	int n; //lucky set 원소 갯수
	int must; //반드시 포함해야 될 수
	int start = 0, stop = 0; //unlucky가 될 수 있는 수들의 처음(start)와 끝(stop)
	int ans = 0; //구간의 갯수

	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}
	cin >> must;

	sort(v.begin(), v.end()); //lucky set 오름차순

	//lucky set안에 연속된 두 수를 묶어서 must가 존재하는지 판단한다.
	for (int i = 0; i < v.size() - 1; i++) {
		if (v[i] < must && must < v[i + 1]) {
			start = v[i] + 1;
			stop = v[i + 1] - 1;
			break;
		}
	}

	if (start == 0 && stop == 0) { //두개로 나눈 구간 안에 must가 들어가 있지 않은 경우
		if (must < v[0]) { //구간 밖에(lucky set에 최솟값보다 must가 작은 경우) must가 존재하는 경우
			start = 1; //시작은 1
			stop = v[0] - 1; //끝은 lucky set에 최솟값보다 1 작은 수
		}
	}

	if (start != 0 && stop != 0) {
		ans = (stop - must + 1) * (must - start) + (stop - must); //must보다 작은 경우는 (stop - must + 1) * (must - stop), must보다 큰 경우는 (stop - must)
	}

	cout << ans;
}