Boj 19941 c++ 햄버거 분배

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

햄버거 분배 Silver 3

 

 

옛날에 풀었던 문제인데, 풀이를 못 떠올렸다.

그리디 문제를 여러 개 더 풀어봐야겠다.

 

문제는 간단하다.

햄버거와 사람의 위치 정보를 담은 문자열과 각 사람당 햄버거를 집을 수 있는 최대 거리를 이용하여

햄버거를 먹을 수 있는 사람의 최댓값을 구하는 문제이다.

 

이쯤에서 그리디 알고리즘 문제의 핵심 풀이법을 상기할 필요가 있다.

부분 문제에서의 최적해는 전체 문제에 대해서도 최적이며, 선택을 번복할 필요가 없다.

 

이 논리를 이용하여 생각해야 하는데,,,

 

처음에 생각했던 풀이는 한 사람당 왼쪽, 오른쪽을 기준으로 사람이 더 적은 쪽의 먹을 수 있는 햄버거 중 가장 멀리 있는 햄버거를 먹도록 하는 것이였다.

 

하지만 '사람이 더 적은 쪽'을 매번 계산하는 것이 비효율적일 뿐만 아니라 올바른 판단기준이 아니다. 이는 매번 최적의 선택이 이후 선택에 영향을 주지 않는다는 조건 또한 만족시키지 않는다.

 

올바른 풀이는 최대한 많은 사람이 햄버거를 먹을 수 있도록 한쪽 방향에서부터 햄버거를 집는 것이다.

먹을 수 있는 범위 k가 주어졌으므로 사람이 있는 인덱스를 i 라고 한다면 i - k 에서 부터 i + k  까지 차례대로 순회하며 햄버거를 먹으면 되는 것이다. 

 

결국 그리디 알고리즘은 복잡한 해법 보다는 간단한 발상이 오히려 정답일 때가 있는 것이라는 것을 깨달았다.

 

전체 코드

#include <iostream>
using namespace std;

int main() {
    int N, k, ans = 0;
    string s;
    cin >> N >> k;
    cin >> s;
    for(int i = 0; i < N; i++) {
        if(s[i] == 'P'){
            for(int j = i-k; j <= i+k; j++) {
                if(j < 0 || j >= N)
                    continue;
                if(s[j] == 'H') {
                    ans++;
                    s[j] = '0';
                    break;
                }
            }
        }
    }
    cout << ans;
}