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

링크

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

19941번: 햄버거 분배

문제

입출력 예제

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>

using namespace std;

int main(void)
{
	string str;
	int answer = 0;

	int n, k;
	cin >> n >> k;

	cin >> str;

	for (int i = 0; i < str.size(); i++)
	{
		if (str[i] == 'P')
		{
			for (int j = i - k; j <= i + k; j++)
			{
				if (j < 0 || j >= n) continue;
				if (str[j] == 'H')
				{
					answer++;
					str[j] = 0;
					break;
				}
			}
		}
	}

	cout << answer;
}

풀이

• 그리디 알고리즘을 사용하였다.
• k만큼 떨어진 햄버거를 먹을 수 있으니 기준이 되는 사람을 i로 가정하면 i-k 부터 i+k 까지
  for문을 반복한다.
• 인덱스를 벗어나면 메모리 오류가 발생하니 j<0 || j>=n 의 조건에서 continue하여 예외처리한다.
• H가 발견되면 answer를 1 올리고 해당 인덱스의 문자를 0으로 바꿔서 다시한번 방문했을 때 햄버거로
  인식하지 못하게 한다.