영어 공부

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXNQOb3avD0DFAXS

SW Expert Academy

 

연속 기간의 '최대 길이'

이분 탐색을 쓰자.

 

gong -> 공백 기간을 저장하는 벡터

0, 1 ~ 2 사이, 2 ~ 3 사이, 3 ~ 4 사이, ....

 

그리고 첫 날부터 n - 1까지 for문을 돈다

-> arr[0]부터 arr[n - 1]까지 

-> arr[1]부터 arr[n - 1]까지

....

 

T T T F F인

left가 정답이 되는 결정문제이다.

 

left의 정답이 i부터 n - 1이 가능하므로!!!

int left = i - 1;

int right = n;

// arr[i]부터 arr[mid]까지 공부 안한 날

dont = gong[mid] - gong[i]

 

p와 dont를 비교하며 이분탐색 진행

 

<소스 코드>

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
 
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int arr[200004];
    int ans;
    // 공백 기간 저장 벡터
    vector<int> gong;
 
    int test;
    cin >> test;
 
    for (int t = 1; t <= test; t++)
    {
        gong.clear();
        int n, p;
        cin >> n >> p;
 
        ans = 0;
        memset(arr, 0, sizeof(arr));
 
        for (int i = 0; i < n; i++)
            cin >> arr[i];
 
        int cnt = 0;
 
        // 0, 1 ~ 2 사이, 2 ~ 3 사이...
        // n개 저장됨
        gong.push_back(0);
        for (int i = 0; i < n - 1; i++) {
            cnt += arr[i + 1] - arr[i] - 1;
            gong.push_back(cnt);
        }
 
        for (int i = 0; i < n; i++) {
            // left가 i부터 n - 1까지 가능하다
            // left i - 1, right = n 잡아야한다.
            int left = i - 1;
            int right = n;
            int tmp_ans = 0;
 
            // T T F F F
            // left가 정답
            while (left + 1 < right) {
                int mid = (left + right) / 2;
                int dont = 0;
                int nokori = p;
                dont = gong[mid] - gong[i];
 
                if (p - dont > 0)
                    nokori = p - dont;
                else
                    nokori = 0;
 
                if (dont <= p) {
                    tmp_ans = arr[mid] - arr[i] + 1 + nokori;
                    left = mid;
                }
                else
                    right = mid;
 
            }
            if (tmp_ans > ans)
                ans = tmp_ans;
        }
        cout << '#' << t << ' ' << ans << '\n';
    }
}