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

문제

---

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

햄버거	사람	햄버거	사람	햄버거	사람	햄버거	햄버거	사람	사람	햄버거	사람
1	2	3	4	5	6	7	8	9	10	11	12

 

위의 상태에서 𝐾=1인 경우를 생각해보자. 이 경우 모든 사람은 자신과 인접한 햄버거만 먹을 수 있다. 10번의 위치에 있는 사람은 11번 위치에 있는 햄버거를 먹을 수 있다. 이 경우 다음과 같이 최대 5명의 사람이 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 11번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음

𝐾=2인 경우에는 6명 모두가 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 3번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 11번 위치에 있는 햄버거

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

 

입력

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

 

출력

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

 

문제 링크

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

 

 

풀이

---

일렬로 쭉 가면서 확인하는 순서만 잘 지켜주면 금방 해결되는 문제다.

햄버거를 왼쪽에서 가장 멀리 떨어진 간격에 있는 사람부터, 오른쪽에 가장 멀리 떨어진 간격에 있는 사람까지 확인하며 할당해주면 된다.

 

햄버거와 사람 둘 중 어느것을 기준으로 해도 상관이 없지만, 필자는 햄버거를 사람한테 할당하는 방식으로 생각했다. ▼

햄버거 맛있겠다

 

예시를 하나 보자.

위의 예시를 그대로 들고 왔다. ▼

햄버거	사람	햄버거	사람	햄버거	사람	햄버거	햄버거	사람	사람	햄버거	사람
1	2	3	4	5	6	7	8	9	10	11	12

 

쭉 순회를 시작하다가, H가 나오면 우선 간격, K 만큼 앞을 확인해본다.

가장 왼쪽부터 확인해야한다.

최대한 멀리있는 것부터 그리디하게 확인해야 최대한으로 배정할 수 있다.

만약에 햄버거가 할당되지 않은 사람이 있다면 햄버거를 할당해주고 해당 인덱스의 루프를 멈춘다. ▼

 

 

왼쪽을 확인했는데 사람이 없거나, 모두 햄버거가 할당된 사람이라면 오른쪽을 동일하게 확인한다.

확인하는 도중 할당되지 않은 사람이 있다면 할당하고 루프를 멈춘다. ▼

 

 

순회를 할 때 순서가 약간 헷갈릴거 같아서 정리를 하면, 아래의 그림과 같이 나오게 된다. ▼

 

 

햄버거(H)를 기준으로 좌, 우로 가는게 아니라 햄버거로부터 가장 왼쪽 간격부터 가장 오른쪽으로 가야한다.

이 과정을 처음부터 끝까지 반복해주면 햄버거를 배정받을 수 있는 사람의 최댓값이 나온다.

 

 

C++ 코드

---

#include <iostream>

using namespace std;

int N, K, answer;
string S;
bool check[20001];

int main() {
    cin >> N >> K;
    cin >> S;

    for (int i = 0; i < N; i++) {
        bool flag = false;

        if (S[i] == 'H') {
            int l, r;

            if (i - K < 0) {
                l = 0;
            } else {
                l = i - K;
            }
            for (int j = l; j <= i - 1; j++) {
                if (S[j] == 'P' && check[j] == false) {
                    answer++;
                    check[j] = true;
                    flag = true;
                    break;
                }
            }

            if (flag) {
                continue;
            }

            if (i + K >= N) {
                r = N - 1;
            } else {
                r = i + K;
            }
            for (int j = i + 1; j <= r; j++) {
                if (S[j] == 'P' && check[j] == false) {
                    answer++;
                    check[j] = true;
                    break;
                }
            }
        }
    }
    cout << answer;
}

 

왼쪽 순회를 시작할 때 주의해야한다.

잘못하면 `중심 -> 왼쪽 끝`으로 순회하게 될 수 도 있다.

물론 그렇게하면 당연히 오답...