[C++] 백준 19941번: 햄버거 분배

문제 링크

19941번: 햄버거 분배

문제 요약

햄버거, 사람으로 이루어진 N개의 자리가 주어진다. 각 사람은 자신으로부터 K 이하 거리의 햄버거를 먹을 수 있다. 이때, 햄버거를 먹을 수 있는 사람의 최댓값을 구해야 한다.

접근 방법

그리디하게 접근하였습니다. 사실 그리디 알고리즘의 경우 증명이 중요하지만, 증명을 하지는 못하고 직감에 의존해서 문제를 해결했습니다. 따라서 아래의 접근 방법에 오류가 있을 수도 있습니다.

일단 가장 왼쪽에 있는 사람부터 순서대로 햄버거를 먹을 수 있는지 판단을 합니다. 해당 사람은 가능한 한 왼쪽에 있는 햄버거를 먹어야 합니다. 이 사람이 가장 왼쪽에 있는 햄버거를 처리하지 않으면, 그 다음 사람은 해당 햄버거와의 거리가 더 멀어지게 됩니다. 이렇기 때문에 왼쪽부터 시작했을 경우, 해당 사람의 인덱스 $i$를 기준으로 $[i - k, i + k]$ 구간 내의 햄버거를 탐색했습니다. 이 구간 내의 햄버거 중에 가장 왼쪽에 있는, 먹히지 않은 상태의 햄버거를 선택하는 식으로 코드를 작성하였습니다.

인덱스가 외곽인 경우, 배열 인덱스의 범위를 벗어나지 않도록 주의해야 합니다.

코드

#include <bits/stdc++.h>

using namespace std;

int arr[20001];

int main(void)
{
	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		char c;
		cin >> c;
		arr[i] = (c == 'H' ? 1 : 2);
	}

	int res = 0;
	for (int i = 0; i < n; i++)
	{
		if (arr[i] == 2)
		{
			for (int j = max(i - k, 0); j <= min(i + k, n - 1); j++)
			{
				if (arr[j] == 1)
				{
					res++;
					arr[j] = 0;
					break;
				}
			}
		}
	}

	cout << res;
	return 0;
}