[백준] 수2 (1059번)

문제

Lucky Set이란 정수의 집합이다.

구간 [A,B]란 A보다 크거나 같고, B보다 작거나 같은 모든 정수가 있는 구간이다. 이때, A와 B는 모두 양수이고, B는 A보다 크다.

구간 [A,B]가 Unlucky가 되기 위해선 구간에 속한 모든 정수가 Lucky Set에 없어야 한다.

Lucky Set과 N이 주어질 때, N을 포함하는 Unlucky 구간의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 Lucky Set에 포함된 숫자의 개수 L이 주어진다. 둘째 줄에는 L개의 수가 주어진다. 이 수는 1,000보다 작거나 같은 자연수이고, L은 50보다 작거나 같은 자연수이다. 그리고 중복되지 않는다. 마지막 줄에는 N이 주어진다. N은 Lucky Set에서 가장 큰 수보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1 복사

4 1 7 14 10 2

예제 출력 1 복사

4

---

예외 처리를 못해서 해맸다.

예제가 적어서 문제 자체도 이해를 못했다.

예제로 문제를 이해해보자.

 

ex1)

4

2 5 6 10

8

이라면 [7,8], [7,9], [8,9]이 가능하므로 3이 정답이다.

 

ex2)
4

5 7 9 10

2

이라면 [1,2], [1,3], [1,4], [2,3], [2,4]가 가능하므로 5가 정답이다.

 

ex3)
4

1 3 5 7

3

이라면 3이 lucky set에 있으므로 0이 정답이다.

 

대충 N이 어느 구간에 속하고 그 속하는 구간에서 N을 포함하는 구간이 몇 개인지 구하면 될 것 같은 느낌이 든다.

따라서 입력으로 들어온 Lucky Set을 정렬한 후 N이 어디에 포함되는지 파악하자.

그 후 그 포함된 구간에서 가능한 가장 작은 수 lo 와 가장 큰 수 hi 를 구한다.

ex1의 입력을 예로 들면 lo = 7, hi = 9이다. 

ex2의 경우는 lo = 1, hi = 4이다.

 

lo, hi, N을 이용해 식을 구해보자면 

lo~ N-1 까지는 hi-N+1개가 가능하고 

N은 hi-N개가 가능하다.

다시 ex2를 예로 들자면 1은 2, 3, 4를 선택할 수 있고 2는 3, 4를 선택할 수 있다는 뜻이다.

최종적인 식은 (N - lo) * (hi - N + 1) + (hi - N)가 되겠다.

 

계속 틀렸습니다가 떠서 이유를 몰랐는데, ex3 경우를 생각 못해서 고생했다.

즉 lucky set 안에 이미 N이 포함되면 정답을 구할 수 없다. 주의하자

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%88%982%20(1059%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int L, N;
vector<int> v;

int main()
{
	cin >> L;
	for (int i = 0; i < L; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}
	cin >> N;

	sort(v.begin(), v.end());

	int lo = 0, hi = 0;
	for (int i = 0; i < v.size(); i++) {
		if (v[i] > N) {
			if (i == 0)
				lo = 1;
			else
				lo = v[i - 1] + 1;
			hi = v[i] - 1;
			break;
		}
		else if (v[i] == N) {
			lo = hi = 0;
			break;
		}
	}
	if (hi == 0 && lo == 0) cout << 0;
	else cout << (N - lo) * (hi - N + 1) + (hi - N);
}