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

백준 19941_햄버거 분배

시간 제한 0.5초(추가 시간 없음), 메모리 제한 256MB

# 조건

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

![[Algorithm/baekjoon_cpp/assets/Pasted image 20230501232934.png]]

• 위의 상태에서 K = 1인 경우를 생각해보자.
  • 이 경우 모든 사람은 자신과 인접한 햄버거만 먹을 수 있다.
  • 10번의 위치에 있는 사람은 11번 위치에 있는 햄버거를 먹을 수 있다.
• 이 경우 다음과 같이 최대 5명의 사람이 햄버거를 먹을 수 있다.
  • 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
  • 4번 위치에 있는 사람: 5번 위치에 있는 햄버거
  • 6번 위치에 있는 사람: 7번 위치에 있는 햄버거
  • 9번 위치에 있는 사람: 8번 위치에 있는 햄버거
  • 10번 위치에 있는 사람: 11번 위치에 있는 햄버거
  • 12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음
•  K = 2인 경우에는 6명 모두가 햄버거를 먹을 수 있다.
  • 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
  • 4번 위치에 있는 사람: 3번 위치에 있는 햄버거
  • 6번 위치에 있는 사람: 5번 위치에 있는 햄버거
  • 9번 위치에 있는 사람: 7번 위치에 있는 햄버거
  • 10번 위치에 있는 사람: 8번 위치에 있는 햄버거
  • 12번 위치에 있는 사람: 11번 위치에 있는 햄버거
• 식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

입력

• 첫 줄에 두 정수 N과 K가 있다.
• 그리고 다음 줄에 살마과 햄버거의 위치가 문자 p(사람)와 H(햄버거)로 이루어지는 길이 N인 문자열로 주어진다.

출력

• 첫 줄에 햄버거를 먹을 수 있는 최대 사람 수를 나타낸다.

제한

• 1 <= N <= 20,000
• 1 <= K <= 10

# 접근 방법

• 입력을 받으며 햄버거의 위치와 사람의 위치를 따로 기록해준다.
• 제일 앞의 사람부터 왼쪽으로 최대 거리에 있는 햄버거를 최우선으로 먹어준다.
• 이후 해당 햄버거를 먹었다는 표시를 해주고, 다음 사람으로 넘어간다.

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

int n, k;
vector<int> hamburger;
vector<int> people;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    string hp;
    int result = 0;
    int idx = 0; // 현재 먹을 수 있는 햄버거의 위치
    cin >> n >> k;
    cin >> hp;
    for (int k = 0; k < hp.length(); k++) {
        if (hp[k] == 'H')
            hamburger.push_back(k);
        else
        {
            people.push_back(k);
        }
    }
    for (int i = 0; i < people.size(); i++) {
        for (int j = idx; j < hamburger.size(); j++) {
            if (people[i] <= hamburger[j]) {
                if (hamburger[j] <= people[i] + k) {
                    idx = j + 1;
                    result += 1;
                    break;
                }
            }
            else {
                if (hamburger[j] >= people[i] - k) {
                    idx = j + 1;
                    result += 1;
                    break;
                }
            }
        }
    }

    cout << result;
    return 0;
}

# 다른 분 풀이

• 굳이 햄버거와 사람을 둘로 나눈 후, 돌려주지 않아도 된다.
• 입력을 모두 받은 후, 햄버거를 기준으로 근처의 사람이 먹을 수 있는지만 체크해주면 된다.
• 0부터 N까지 순회해주면서
  • 햄버거를 만나는 경우만 아래 로직 수행
  • j는 햄버거 인덱스 i - k ~ i + k 까지 돌려주며
  • 사람을 만나면 _ 로 변경 해준 후 다음 햄버거로 넘어간다.

#include<iostream>

#define endl "\n"
using namespace std;

void Answer()
{
    int N, K, answer = 0;
    string burgar;

    cin >> N >> K;
    cin >> burgar;

    for (int i = 0; i < N; i++)
    {
        if (burgar[i] != 'H') continue;

        for (int j = i - K; j <= i + K; j++)
        {
            if (j < 0 || j >= N) continue;
            if (burgar[j] == 'P')
            {
                burgar[j] = '_';
                burgar[i] = '_';
                answer++;
                break;
            }
        }
    }
    cout << answer;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    Answer();
    return 0;
}