취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 19941번 문제인 햄버거 분배이다.
문제는 아래 링크를 확인하자.

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

거리가 K 이하인 햄버거의 최대 매칭을 구하는 문제이다.

맨 왼쪽에 있는 사람서부터 살펴볼 때, 이 사람이 먹을 수 있는 햄버거가 여럿이라면 그중 가장 왼쪽에 있는 햄버거를 선택하여 먹는다면 항상 최선의 경우중 하나를 찾을 수 있다. 그 뒤에 햄버거를 선택할 사람의 선택폭을 최소화하여 줄이기 때문이다.

따라서, 현재 살피고 있는 사람과 햄버거를 가리키는 index 변수를 만들어 greedy하게 탐색하는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

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

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

	int N, K; cin >> N >> K;
	string s; cin >> s;

	int H = 0, P = 0, ans = 0;
	while (s[H] == 'P') {
		H++;
		if (H == N) break;
	}
	while (s[P] == 'H') {
		P++;
		if (P == N) break;
	}

	while (H < N && P < N) {
		if (abs(H - P) <= K) {
			ans++;
			H++;
			P++;
		}
		else {
			if (H < P) H++;
			else P++;
		}

		while (s[H] == 'P') {
			H++;
			if (H == N) break;
		}
		while (s[P] == 'H') {
			P++;
			if (P == N) break;
		}
	}

	cout << ans;
}