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

 

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

19941번: 햄버거 분배

 

# 문제 설명

문자열의 길이 N, 햄버거를 선택할 수 있는 거리 K, 사람(P)과 햄버거(H)의 위치가 문자열로 주어질 때, 햄버거를 먹을 수 있는 사람의 최대 수를 출력한다.

 

# 문제 풀이

왼쪽부터 차례로 문자열을 읽어나갈 때, 왼쪽의 사람이 햄버거를 먹을 수 있는데 먹지 않는 경우, 손해가 발생한다. 따라서 왼쪽부터 읽어나가며 사람이 햄버거를 먹을 수 있는 경우의 수를 count 한다.

필자는 두 개의 queue에 각각 사람과 햄버거의 index를 넣어서 front 값을 비교하며 값을 지워나갔다.

또 다른 방법으로는, 단순 반복문으로 문자열을 읽어나가며 사람(P)이 나올 경우 ( i-K, i+K )의 범위를 살펴본 후 방문하지 않은 햄버거(H)가 있다면 방문처리 후 ans++를 해주는 식으로 보다 단순하게 해결 가능하다.

 

# 정답 코드

#include <iostream>
#include <queue>
using namespace std;

int n, k;
string s;
queue<int> h, p;
int ans = 0;

int main() {

	cin >> n >> k >> s;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'H') h.push(i);
		else p.push(i);
	}

	while (!p.empty() && !h.empty()) {
		if (h.front() + k < p.front()) h.pop(); // hamburger eaten is impossible
		else if (h.front() < p.front()) { // eat left
			h.pop();
			p.pop();
			ans++;
		}
		else if (p.front() + k >= h.front()) { // eat right
			h.pop();
			p.pop();
			ans++;
		}
		else p.pop(); // eating hamburger is impossible
	}
	cout << ans;
}