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

문제

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

백준 19941

백준 19941

 

문제 내용

햄버거 H와 사람 P의 순서가 표시된 문자열이 주어진다.

사람은 자기 주변으로 k만큼 거리 안에 있는 햄버거만 먹을 수 있다.

최대한 많은 사람이 햄버거를 먹을 수 있도록 할 때, 최대 사람 수를 구하면 된다.

 

문제 풀이

greedy한 문제이다.

사람을 기준으로 (-k~k) 범위 안에 있는 햄버거 중 가장 좌측에 있는 것을 먹도록 하면 된다.

햄버거를 먹으면 그 배열의 원소를 H나 P가 아닌 문자로 바꾸고 계속 탐색을 진행하면 된다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


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

	//입력
	int n, k;
	cin >> n >> k;
	vector<char>arr(n);
	for (int i = 0; i < n; i++) cin >> arr[i];

	//문제 해결
	int count = 0;
	for (int i = 0; i < n; i++) {
		if (arr[i] == 'P') {
			for (int j = i - k; j <= i + k; j++) {
            	 		//배열 범위 밖으로 나가는 것 방지
				if (j<0 || j>n - 1) continue;
				
				if (arr[j] == 'H') {
					count++;
					arr[j] = 'Q'; //H,P이외의 문자로 변경
					break;
				}
			}
		}
	}

	cout << count << '\n';
}