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

🌱문제 설명

19941번 햄버거 분배

문제

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

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

위의 상태에서 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인 문자열로 주어진다.

---

출력

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

풀이

#include<iostream>
using namespace std;

int main(){
    int N,K; // N = 문자열 길이, K = 먹을 수 있는 햄버거 거리
    cin >> N >> K;
    
    string str; // 문자열 
    cin >> str;
    
    int count = 0; // 햄버거를 먹을 수 있는 사람 수
    
    for(int i = 0; i < N; i++){
        if(str[i] == 'P'){ // 현재 위치가 사람인 경우
            // 왼쪽으로 최대 K만큼 이동하여 햄버거 찾기
            for(int j = i - K; j <= i + K; j++){
                if(j >= 0 && j < N && str[j] == 'H'){ // 배열 범위를 벗어나지 않고 햄버거를 찾은 경우
                    count++;
                    str[j]='x';//이미 먹은 햄버거는 x로 해서 다름 사람이 안먹도록
                    break; // 햄버거를 한 번 먹으면 더 이상 찾지 않음
                }
            }
        }
    }
    
    cout << count << endl;
    
    return 0;
}

🔥문제 요약:

입력 받은 햄버거 문자열에서 사람 P가 K거리의 햄버거를 먹을 수 있을 때. 햄버거를 먹을 수 있는 최대 사람 수 구하기

🤔 생각해야 할 점

1. HP문자열에서 H는 햄버거 P는 사람이다.
2. P는 k거리 안에 있는 햄버거만 먹을 수 있다.
3. 다른 P가 이미 먹은 햄버거는 먹지 못한다.

🔥 풀이 과정

1. 문자열 길이, K, 문자열 배열 입력받기

→ 이중 반복문으로 검사( 검사할 햄버거의 범위는 i-k ~ i+K )

2. 문자열을 검사해서 현재 인덱스가 P이면 k의 범위 내에 햄버거가 있는지 검사
3. H(햄버거)가 있으면 먹을 수 있는 사람 수를 늘려준다.

⭐️ 먹은 햄버거는 다른 문자로 바꿔 줘야 다른 P가 다시 먹지 않는다! ⭐️

• 코드 설명

✅ 문자열 길이와 먹을 수 있는 거리 K, 햄버거와 사람 문자 배열 입력받기

	int N,K; // N = 문자열 길이, K = 먹을 수 있는 햄버거 거리
  cin >> N >> K;
    
  string str; // 문자열 
  cin >> str;

✅

1. 문자열 길이 내에서 사람을 뜻하는 “P” 를 찾는다.

2. P를 찾았다면 해당 인덱스에서 K만큼의 거리에 있는 햄버거 "H" 를 찾는다.

( 범위를 벗어나는 인덱스를 찾지 않도록 범위를 설정)

3. 찾았다면 count를 증가시키고 이미 먹은 햄버거를 다시 찾지 않도록 문자열을 바꿔준다.

    for(int i = 0; i < N; i++){
        if(str[i] == 'P'){ // 현재 위치가 사람인 경우
            // 왼쪽으로 최대 K만큼 이동하여 햄버거 찾기
            for(int j = i - K; j <= i + K; j++){
                if(j >= 0 && j < N && str[j] == 'H'){ // 배열 범위를 벗어나지 않고 햄버거를 찾은 경우
                    count++;
                    str[j]='x';//이미 먹은 햄버거는 x로 해서 다름 사람이 안먹도록
                    break; // 햄버거를 한 번 먹으면 더 이상 찾지 않음
                }
            }
        }
    }