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

1. 개요

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

19941번: 햄버거 분배

1-1. 설명

기다란 벤치 모양 식탁에 사람과 햄버거가 아래와 같이 간격으로 놓여있다. 사람들은 자신 위치에서 거리가 K 이하인 햄버거를 먹을 수 있다. 

식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K, 사람과 햄버거 위치가 주어졌을 때 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫 줄에 정수 N과 K가 주어지며, N은 1 이상 20,000 이하, K는 1 이상 10 이하

 - 다음 줄에 사람과 햄버거 위치가 문자 P, H로 이루어지는 길이 N인 문자열 주어짐

---

2. 구현

2-1. 풀이

테이블에서 P가 나왔을 때, index - K에서 index + K 범위까지 반복문을 돌려 햄버거가 있으면 +1 해준다. 그렇게 어렵지 않은 문제였다. 

2-2. 코드

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

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

    int N, K, index = 0, result = 0;
    string table;
    bool check[20000] = {false, };
    cin >> N >> K >> table;
    
    for (char ch : table) {
        if (ch == 'H') {
            index += 1;
            continue;
        }

        // 사람 일 때
        for (int i = index - K; i <= index + K; i++) { // P기준 -K ~ +K만큼 햄버거 확인
            if (table[i] != 'H' || check[i]) continue;
            // P거나 이미 먹은 햄버거라면 continue
            result += 1;
            check[i] = true;
            break;
        }
        index += 1;
    }
    cout << result;
    return 0;
}