[1059] 좋은 구간

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

1059번: 좋은 구간

<문제>

입력을 받고, 정렬한다. 정렬을 한다면

선형적으로 탐색을 진행하다 포함해야하는 숫자 n을 초과하는 시점에 break를 걸어줌으로써

구간 시작점의 최소값인 start와 구간 종료지점의 최대값인 end를 찾을 수 있다.

 

한가지 주의할점은 start = v[i-1], end = v[i]가 아닌,(off by one)

구간내 수가 입력된 수에 속하지 않아야 하기에

start = v[i-1] + 1, end = v[i] - 1으로 설정해 주어야 한다. 

 

좋은 구간이 되기 위해서는, 구간의 길이가 2인것부터 탐색하면 되겠다.

그렇기에 2중for에서 j의 시작점을 i+1로 설정해주고 정답을 업데이트해나가면 된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, t;
int main(void) {
    int i, j;
    cin >> n;
    vector<int> v(n);
    for (i = 0; i < n; i++) cin >> v[i];
    cin >> t;
    sort(v.begin(), v.end());
    for (i = 0; i < n; i++)
        if (v[i] > t) break;
    int start = v[i - 1] + 1, end = v[i] - 1;
    int answer = 0;
    for (i = start; i < end; i++) {
        for (j = i + 1; j <= end; j++) {
            if (i <= t && t <= j) answer++;
        }
    }
    cout << answer;
    return 0;
}