[백준] 햄버거 분배

https://www.acmicpc.net/problem/19941

19941번: 햄버거 분배

전형적인 그리디 문제이다. 처음에 문제를 이해하지 않고 풀려고 한다면 사람에 대해 햄버거를 매칭하며 브루트 포스 식으로 최대 매칭 값을 구하려고 할 것이다. 하지만 조금만 더 고민해보면 만약 어떤 사람에 대해 K 범위 내의 매칭될 수 있는 햄버거가 여러 개라면 최대한 현재 진행 중인 방향의 역에 있고(예를 들어 오른쪽으로 사람을 매칭해나가면 최대한 왼쪽에 있는 햄버거를 매칭해주기)는 햄버거를 매칭해주면 된다.

 

탐색은 사실 햄버거 기준으로 해도되는데, 난 접근하기에 사람으로 기준을 삼는 게 편해서 아래와 같이 풀었다.

 

#include <iostream>
#include <queue>
using namespace std;
queue<int> hamburgers;
queue<int> ppl;

int main() {
    int N, K, answer = 0;
    string line;
    cin >> N >> K;
    cin >> line;


    for(int i = 0;i < N;i++) {
        if(line[i] == 'H') {
            hamburgers.push(i);
        }
        else {
            ppl.push(i);
        }
    }

    while(!ppl.empty()) {
        int person = ppl.front();
        ppl.pop();

        while(!hamburgers.empty() && person - hamburgers.front() > K) {
            hamburgers.pop();
        }

        if(hamburgers.empty()) break;

        if(person > hamburgers.front() && person - hamburgers.front() <= K) {
            hamburgers.pop();
            answer++;
        }
        else if(person < hamburgers.front() && hamburgers.front() - person <= K) {
            hamburgers.pop();
            answer++;
        }
    }

    cout << answer << '\n';
    return 0;
}