2022-05-14 알고리즘 문제(백준 19941 햄버거 분배)

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

19941번: 햄버거 분배

문제

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

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

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

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

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

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

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

---

#include <iostream>
using namespace std;
int main(void){
    char arr[20000];
    bool visited[20000] = {false, };
    int n,k;
    cin >> n >> k;
    for(int i = 0;i<n;i++){
        cin >> arr[i];
    }
    int cnt = 0;
    for(int i = 0;i<n;i++){
        if(arr[i] == 'P'){
            for(int j = i-k;j<=i+k;j++){
                if(visited[j] == false && arr[j] == 'H'){
                    cnt++;
                    visited[j] = true;
                    break;
                }
            }
        }
    }
    cout << cnt;
}

오늘 배운 점 : 처음에 bool 배열을 선언하고 초기화를 안한 상태로 제출하여서 틀렸습니다를 받았다.

C++ Bool형 값은 전역변수로 선언시 0으로 초기화되지만, 지역변수의 경우 꼭 초기화를 해줘야 한다.(안하면 쓰레기 값 들어감)