[백준 1059] 좋은구간(C++)

📕문제

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

✔예제 입력 1

4
1 7 14 10
2

✔출력 1

4
// [2,3],[2,4],[2,5],[2,6]

❤문제 해석

• N을 포함한 좋은 구간의 개수란?
  • S집합에 원소들이 없고, N을 무조건 포함한 것
• S집합에다가 N을 삽입하고 정렬을 하면 N의 구간이 나온다.
• 여기서 만약 N을 삽입했는데 N이 집합 안에 이미 있다면 자동으로 0을 출력하고 프로그램을 종료
  • 좋은 구간이 나올 수가 없다.
• 그리고 만약 N이 집합 S의 최댓값보다 크다면 자동으로 0을 출력하고 프로그램을 종료
  • 좋은 구간이 나올 수 가없다.
• 이 경우를 제외하고는 좋은 구간이 나올 수 있다.
  • 집합 s에서 N을 찾고 N보다 한 칸  앞 뒤에 있는 것을 변수로 저장
    • 내 코드에서는 start와 finish로 저장했음.
• 좋은 구간의 개수
  • start+1부터 n까지, start+2부터 n까지 ,,,,,, n-1부터 n까지  ++
  • n부터 n+1, n부터 n+2 ~~~~~ n부터 finish-1까지를 더하면 좋은 구간의 개수가 나온다.

 

📃코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//첫째줄은 S의 크기가 주어지고, 둘 째 줄에는 집합의 원소 셋째줄에는 n이주어진다.
// n을 포함한 좋은 구간의 개수를 출력   A<=x<=B일떄 모든 정수 x가 집합 S에 속하지 않는다.
int main()
{

    int t, n, num, start, finish;
    cin >> t;
    vector<int> ary;
    for (int i = 0; i < t; i++)
    {
        cin >> num;
        ary.push_back(num);
    }
    cin >> n;
    for (int i = 0; i < ary.size(); i++)
    {
        if (ary[i] == n)
        {
            cout << 0;
            return 0;
        }
    }
    // n을 포함한 좋은 구간의 개수를 출력해야함. 그러면 n이 어딨는지 판별해야함.
    ary.push_back(n);

    sort(ary.begin(), ary.end()); //이러면 ary에서 n에 위치를 알게될거임.
    start = n;
    for (int i = 0; i < ary.size(); i++)
    {
        if (ary[i] == n)
        {
            start = ary[i - 1];
            finish = ary[i + 1];
        }
    }
    // start finish 뽑고. 그 안에서 n을 포함하는 좋은 구간을 찾아야 하지요.
    int count = 0;
    // cout<<start<<" "<<finish<<endl;
    for (int i = start + 1; i <= n; i++)
    {
        for (int j = n; j <= finish - 1; j++)
        {
            if (i == j)
                continue;
            count++;
        }
    }
    cout << count;
}

---

느낀 점

문제를 잘 해석해서 좋은 구간에 대한 개념을 잡고, 그에 대한 개수를 구할 수 있다면 쉽게 풀 수 있는 문제이다.
특별하게 알고리즘이 필요한 문제는 아니었다. 구현정도!