[백준/C,C++] 1059번: 좋은 구간

www.acmicpc.net/problem/1059

1059번: 좋은 구간

풀이

예제 입력 1의 경우 1 7 14 10 의 정수가 입력되었고, 2를 포함하는 좋은 구간을 구해보면

 

[2, 3], [2, 4], [2, 5], [2, 6]이 나옵니다.

 

n이 3이라고 쳐보면,

 

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

[3, 4], [3, 5], [3, 6]

이 나오죠.

 

4일 경우

[2, 4], [2, 5], [2, 6]

[3, 4], [3, 5], [3, 6]

[4, 5], [4, 6]

이고,

 

5일 경우

[2, 5], [2, 6]

[3, 5], [3, 6]

[4, 5], [4, 6]

[5, 6]

입니다.

 

정수 집합 S를 오름차순으로 정렬한 뒤 n보다 큰 원소를 찾습니다.

 

그 후 직전의 원소에 1을 더한 값을 구간의 시작점(s), 큰 원소에 1을 뺀 값을 구간의 끝점(e)이라고 보고

 

(n - s) * (e - n + 1) + (e - n)의 식으로 좋은 구간의 개수를 구할 수 있습니다.

 

 

예제 입력으로 다시 보면..

 

5일 경우 (s가 2, e가 6, n이 5) → (5 - 2) * (6 - 5 + 1) + (6 - 5) = 7입니다.

[2, 5], [2, 6] → (경우의 수가 e - n + 1로 2개)

[3, 5], [3, 6] → (경우의 수가 e - n + 1로 2개)

[4, 5], [4, 6] → (경우의 수가 e - n + 1로 2개)

[5, 6] → (경우의 수가 e - n으로 1개)

 

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(void)
{
    int L; cin >> L;
    vector<int> v(L);

    for (int i = 0; i < L; i++) {
        cin >> v[i];
    }
    v.push_back(0);

    int n; cin >> n;
    int s, e;
    bool b = true;

    sort(v.begin(), v.end());
    for (int i = 1; i < L + 1; i++) {
        if (n == v[i]) b = false;
        else if (n < v[i]) {
            s = v[i - 1] + 1;
            e = v[i] - 1;
            break;
        }
    }

    if (b) cout << (n - s) * (e - n + 1) + (e - n);
    else cout << 0;

    return 0;
}

반례

Input

1

5

2

Output

5

 

Input

5

1 2 2 3 6

4

Output

1

 

Input

6

1 6 77 82 999 1000

500

Output

208581

 

Input

10

77 1 8 950 12 69 230 500 420 876

Output

4921