[백준 19941] 햄버거 분배

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

생각보다 쉬운 문제였다. 예선때도 시간내에 무난하게 풀었고, 여러 방향으로 사고를 해봐야 된다는 사실을 많이 느꼈다.

이 문제의 경우 부분 문제를 받을 수 있는 풀이와 만점을 받을 수 있는 풀이가 있다. 둘다 모두 작성하도록 하겠다.

1. 40점 풀이

먼저 제가 이 문제를 보고 최대값을 구하는 문제인 것을 보고 dp를 사용하겠구나라고 추측했다. 점화식을 세우는 것은 나쁘지 않았다.

$$ solve(i,j) = 현재 i번째 위치이고, 마지막으로 먹은 햄버거가 j번째 일때$$

$$ solve(i, j) = \begin{cases} solve(i+1,j), \mbox{if(arr[i] == H)} \\ max_{max(j,i-k) \le w \le i}(solve(i+1, w)+1), \mbox{if(arr[i] == P)} \end{cases}$$

이런식으로 점화식을 작성할 수 있고 시간 복잡도는 \(O(n^2)\) 이다. 하지만 부분 점수 \(40\)점의 케이스는 최대 \(N\)이 \(1000\)까지 밖에 들어오지 않아 가능하다.

2. 100점 풀이

문제를 풀 때 dp 점화식을 요리조리 바꾸어 보면 시간복잡도를 줄일 수 있지 않을까 했다. 하지만 \(20\)분 정도 삽질 결과 도무지 방법이 떠오르지 않았다.

 

그래서 문제를 다시 사고하기로 했다. 따지고 보면 사람당 제일 멀리 있는 햄버거만 먹는 것이 최선이 아닐까? 라고 생각해보았다. 그러자 \(100\)점 맞게 되었다.

3. 소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <list>
#include <stack>
#include <queue>
using namespace std;
 
int n, k;
string str;
 
vector<int> P;
queue<int> H;
 
int main() {    
    cin >> n >> k;
    cin >> str;
    
    for(int i=0; i < n; i++){
        if(str[i] == 'H') H.push(i);
        if(str[i] == 'P') P.push_back(i);
    }
    
    int ans = 0;
    for(int pos : P){
        int l = max(0, pos-k), r = min(pos+k, n-1);
        while(!H.empty()){
         int top = H.front();
             if(l <= top && top <= r){
                 H.pop();
                 ans++;
                 break;
             }else if(top > pos) break;
             else if(top < pos) H.pop();
         }
    }
    
    cout << ans;
    
    return 0;
}