Codeforces #1506B Partial Replacement

문제

https://codeforces.com/problemset/problem/1506/B

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        int i = s.find("*");
        int j = s.rfind("*");
        s[i] = s[j] = 'x';
        while(i < n){
            int star = 0;
            int dist = i+k+1;
            bool valid = true;
            int l;
            for(l = i+1; l < min(n, dist); l++){
                if(s[l] == '*'){
                    star = l;
                }
                else if(s[l] == 'x'){
                    valid = false;
                }
            }
            if(star && valid){
                s[star] = 'x';
                i = star;
            }
            else{
                i = l;
            }
        }
        int cnt = 0;
        for(i = 0; i < n; i++) if(s[i] == 'x') cnt++;
        cout << cnt << "\n";
    }
    return 0;
}

대회 때 문제를 재대로 이해하지 못해서 어렵게 느껴졌던 것 같다. 예제를 조금만 풀어보면 그리디 직관을 얻을 수 있었다.