백준 26976 - Feeding the Cows

문제링크 : https://www.acmicpc.net/problem/26976

유사코 문제이다

n을 훑으면서 string s 를 진행하는데

각 i마다
i - k ~ i+k 를 탐색하면서
ans 에 해당 patch가 없으면
가능한 제일 오른쪽에 해당 patch를 새로 두게 하면된다.

이때 변수 gok 와 hok 를
새로 둔 patch 의 idx + k 로 정의한다

이걸 써서 불필요한 탐색부분을 줄여주면 AC를 받게된다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<cstring>
#include<queue>
using namespace std;

int main(){ 
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){
        int n,k;cin>>n>>k;
        string s;cin>>s;
        vector<char> ans(n,'.');
        int gok = 0;
        int hok = 0;
        int cnt = 0;
        for(int i=0;i<n;i++){
            char now = s[i];
            if(now=='G'){
                if(i<gok) continue;
            }else{
                if(i<hok) continue;
            }
            int l = max(0,i-k);
            int r = min(i+k,n-1);
            bool flag = false;
            for(int t=l;t<=r;t++){
                if(ans[t]==s[i]){
                    flag = true;break;
                }
            }
            if(flag) continue;
            while(ans[r]!='.') r--;
            ans[r]=s[i];
            cnt++;
            if(s[i]=='G') gok=r+k;
            else hok=r+k;
        }
        cout<<cnt<<"\n";
        for(char a : ans) cout<<a;
        cout<<"\n";
    }
    
}