햄버거 분배( BOJ 19941 )

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

19941번: 햄버거 분배

 

문제 파악하기

햄버거와 사람이 번갈아 위치했을 때, 햄버거를 먹을 수 있는 사람의 최댓값을 구하는 문제입니다. 각각의 사람들은 자신의 위치에서 K만큼 떨어진 위치의 햄버거까지 먹을 수 있으며, 누군가 먹은 햄버거는 먹을 수 없습니다. 이렇게 모든 사람이 동일한 범위(K) 안의 햄버거를 먹을 수 있다면 우리는 가장 왼쪽에 위치한 햄버거부터 하나씩 사람에게 할당하는 방법을 사용할 수 있습니다.

 

문제 해결하기

가장 왼쪽에 위치한 햄버거부터 하나씩 사람들에게 할당하면 햄버거를 먹을 수 있는 최대 인원 수를 구할 수 있을까요? 정답은 구할 수 있습니다. 이는 모든 사람이 동일한 범위 내의 햄버거를 먹을 수 있기 때문입니다. 가장 왼쪽의 햄버거를 먹을 수 있는 사람 중에서 가장 왼쪽에 위치한 사람이 햄버거를 먹어야 다음 사람이 다른 위치의 햄버거를 먹을 수 있는 가능성이 커지게 되며, 이는 햄버거를 먹을 수 있는 인원의 최댓값을 구할 수 있게 됩니다. 그럼 가장 왼쪽의 사람이 가장 왼쪽의 햄버거를 먹는 알고리즘으로 문제를 해결해봅시다.

 

소스코드

#include <stdio.h>
#include <string.h>
#define NMAX 20010
 
int N, K;
char inp[NMAX];
 
int cnt;
int check[NMAX];
 
int main() {
    // 입력
    scanf("%d %d", &N, &K);
    scanf("%s", inp);
 
    // 탐색(그리디)
    for(int i=0;i<N;i++) {
        if(inp[i] == 'H') continue;
 
        for(int j=i-K;j<=i+K;j++) {
            if(j<0 or j>=N) continue;
 
            if(inp[j] == 'H' and !check[j]) {
                cnt++;
                check[j] = 1;
                break;
            }
        }
    }
 
    // 출력
    printf("%d", cnt);
}

후기

가장 기본적인 그리디 알고리즘 문제입니다. 그리디 알고리즘을 처음 배우는 사람에게 소개하면서 알려주는 기본적인 문제라고 생각합니다.