백준 19941 햄버거 분배 C++

문제 보고 그냥 단순하게 왼쪽부터 차례대로 전부 탐색

 

시간제한이 0.5초이고, n이 20000개, k가 10이다.

 

최소한 20000 * 10하면 이십만번 탐색하면 0.5초도 안걸린다고 생각해서 전부 탐색해도 된다.

 

답

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n,k;
    cin>>n>>k;
    string a;
    cin>>a;
    vector<bool> visited(n,false);
    int ans=0;
    for(int i=0;i<a.size();++i){
        if(a[i]=='P'){
            bool state=false;
            int ptr=i-k;
            if(i-k<0){
                ptr=0;
            }
            for(int j=ptr;j<i;++j){
                if(!visited[j]&&a[j]=='H'){
                    visited[j]=true;
                    state=true;
                    ++ans;
                    break;
                }
            }
            if(!state){
                for(int j=i+1;j<=i+k&&j<n;++j){
                    if(!visited[j]&&a[j]=='H'){
                        visited[j]=true;
                        ++ans;
                        break;
                    }
                }
            }
        }
    }
    cout<<ans;
}