[ 백준 / C++ ] 19941 : 햄버거 분배

[ 문제 ]

 

19941번: 햄버거 분배

 

[ 접근방법 ]

 

제일 왼쪽에 있는 사람부터 시작하여 최대한 왼쪽에 위치한 햄버거를 먹는 방식으로 문제를 접근한다.

 

시간복잡도는 O(NK) 이다.

 

[ 소스코드 ]

 

#include <iostream>
#include <algorithm>

using namespace std;

int n, k, ans;
string str;

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

    cin >> n >> k >> str;

    for(int i = 0; i < n; i++){
        if(str[i] == 'P'){
            for(int j = max(0, i - k); j <= min(n - 1, i + k); j++){
                if(str[j] == 'H'){
                    str[j] = 'N';
                    ans++;
                    break;
                }
            }
        }
    }

    cout << ans;

    return 0;
}