[Softeer/소프티어][level3] 스마트 물류 (C++)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=414&sw_prbl_sbms_sn=18270

Softeer

 

[난이도] level3
[유형] Greedy

[풀이]
로봇과 부품의 index를 각각 저장한 뒤,
앞쪽 로봇부터 부품을 할당할때 가능하면 앞쪽 부품을 할당하는 것이 가장 유리합니다.
이를 위해 부품의 index는 queue에 저장해서 앞쪽 부터 순차적으로 꺼내면서 사용해주면 됩니다.

 

 

#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
int N,K;
vector<int> p;
queue<int> q;
string s;
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<N;i++) {
        char c;
        scanf(" %c",&c);
        if(c=='P') p.push_back(i);
        else q.push(i);
    }
    int ans=0;
    for(auto r : p){
        while(!q.empty()){
            int i = q.front(); 
            if(abs(r-i)<=K) {
                ans++;
                q.pop();
                break;
            }else if(r>i) q.pop();
            else break;
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/스마트_물류.cpp