[백준(BOJ)] 햄버거 분배(19941번)_C++

그렇게 어렵지는 않은 문제였다.

자신의 사정거리안에 먹을 수 있는 햄버거있는지 판단하는 문제다.

 

주어진 문자열을 탐색할 때 어디서부터 탐색하는지가 중요하다.

만일 왼쪽부터 탐색한다면 가장 왼쪽에 있는 햄버거는 가장 왼쪽에 있는 사람이 차지하는 방식으로 구현해야한다.

당연한 말처럼 들리겠지만 최적의 해를 구하는 방법이 이 방법이다.

즉, 임의의 사람이 먹을 수 있는 햄버거를 탐색할 때 이또한 왼쪽에서부터 탐색해야 한다는 이야기이다.

 

시간복잡도는 O(n*(2*k + 1))이므로 최악의 경우 20000*21이다.

시간제한을 통과하기 충분하다.

 

---

정답 코드

#include <iostream>

using namespace std;

int n, k, answer;
string s;
bool eat[20100];

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

    cin >> n >> k >> s;

    s = "0000000000" + s + "0000000000";

    for (int i = 10; i < n + 10; i++){
        if (s[i] == 'P'){
            for (int j = i - k; j <= i + k; j++){
                if (s[j] == 'H' && eat[j] == false){
                    eat[j] = true;
                    answer++;
                    break;
                }
            }
        }
    }

    cout << answer;
}