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

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

길이가 N인 식탁에 햄버거와 사람이 간격에 맞춰 존재한다. 사람들은 자신의 위치에서 거리가 K 이하인 햄버거를 먹을 수 있다. 이때 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 20,000
• 1 ≤ K ≤ 10

 

문자열을 반복문을 통해 접근하도록 코드를 짜야 한다.

 

햄버거를 선택할 수 있는 거리가 K로 일정하기 때문에 각 사람마다 자신의 위치에서 K를 뺀 거리에 있는 햄버거부터 K를 더한 거리에 있는 햄버거까지 접근할 수 있다. 반복문이 진행될수록 오른쪽으로 이동하므로 (왼쪽 > 오른쪽) > (먼 > 가까운) 우선순위를 지켜서 먹으면 햄버거를 먹을 수 있는 사람의 수를 최대한 늘릴 수 있다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, K, 사람과 햄버거의 위치 입력받기
2. 반복문을 통해 사람이 자기와 가장 멀고(K만큼), 왼쪽에 있는 햄버거를 먹도록 하기
   1. 사람이 아닌 경우 continue
   2. 먹은 햄버거는 H 대신 다른 문자로 대체하고 햄버거를 먹은 사람 수 갱신
3. 햄버거를 먹은 사람 수의 최댓값을 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

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

int n,k,ans;
string str;

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

    cin >> n >> k >> str;
    for (int i=0; i<n; i++) {
        if (str[i]!='P') continue;

        for (int j=i-k; j<=i+k; j++) {
            if (0<=j && j<n && str[j]=='H') {
                str[j]='.';
                ans++;
                break;
            }
        }
    }
    cout << ans;
}