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

문제

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

풀이

Greedy는 역시나 어렵다ㅜ 어렵게 생각하지 말고, 익숙해지기

처음 접근)

저런 식으로 인접리스트 배열을 만들어서 ➡️배열 사이즈가 작은 순서대로 정렬해서 ➡️먹은 사람 pop하는 방식을 생각했는데 구현도 어렵고 알고리즘 자체도 꼬였다.

정답)
Greedy는 현재 조건에서 최선을 선택하면 됨 =>범위대로 탐색하면서 먹을 수 있으면 먹고, 그 햄버거 자리를 다른 사람이 못 먹게 다른 문자로 바꿔버리면 됨

쉽게 생각하면 엄청 간단한 문제였다.

코드

#include <iostream>
#include <string>

using namespace std;

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

	string str;
	int N, K;
	cin >> N >> K;
	cin >> str;
	int ans = 0;
	for (int i = 0; i < N; i++) {
		if (str[i] == 'P') {
			for (int j = i - K; j <= i + K; j++) {
				if (j >= 0 && j < N && str[j] == 'H') {
					str[j] = '-';
					ans++;
					break; //먹은 후에는 break 걸어서 다른 사람 먹을 수 있도록!
				}
			}
		}
	}

	cout << ans;

	return 0;
}