2631 - 줄세우기

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

2631번: 줄세우기

생각해보기

1. 아이들이 가장 안움직여도 되는 경우를 따지자.
2. 결국 번호 순서를 오름차순으로 정렬시키는게 핵심이다.
3. lis(가장 긴 증가 수열)을 이용하자.

코드

#include<iostream>

using namespace std;

int N,K;
int arr[200001];
int chk[100001];

void input(){
    cin>>N>>K;
    for(int i=0;i<N;++i){
        cin>>arr[i];
    }
}

void solution(){
    int ans = 0;
    int l=0, r=0;

    while(r<N){
        ++chk[arr[r]];

        while(chk[arr[r]] > K){
            --chk[arr[l++]];
        }

        ans = max(ans, r-l+1);
        ++r;
    }
    
    cout<<ans<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    solution();

    return 0;
}