백준 23350 K 물류창고 / C++

문제 : 23350

풀이 point

먼저, 우선순위대로 처리해야하기 때문에 1~N까지의 우선순위를 가진 컨테이너가 각각 몇개인지를 파악해야한다. 그 다음 해당 우선순위를 처리할 때 다른 우선순위를 가진 컨테이너가 등장하면 뒤로 돌리고 다음 컨테이너를 확인한다.

우선순위가 같으면 무게가 작은 것을 위로 올리도록 해야한다. 이를 위해 스택의 가장 위에 있는 컨테이너의 무게와 현재 올릴 컨테이너의 무게를 비교해가며 적절한 위치에 컨테이너를 삽입해줘야 한다.

풀이 방법

컨테이너 벨트는 큐를 통해 진행하고, 컨테이너를 놓기 위한 공간은 스택으로 하여 마지막 값을 하나씩 빼기 쉽도록 한다.

코드

//백준 23350, K 물류창고

#include <iostream>
#include <queue>
#include <stack>

std::queue<std::pair<int, int>> q;

int freq[101];
int N, M;
int sum = 0;

void rotate() {
  auto num = q.front();
  q.pop();
  q.push(num);
  sum += num.second;
}

void check(std::stack<int>& s, int w) {
  std::stack<int> tmpS;

  while(!s.empty() && w > s.top()){
    sum += s.top();
    tmpS.push(s.top());
    s.pop();
  }

  s.push(w);
  sum += w;
  
  while (!tmpS.empty()) {
    sum += tmpS.top();
    s.push(tmpS.top());
    tmpS.pop();
  }
}

void solve() {
  int prirotiy = M;
  std::stack<int> s;
  while(prirotiy != 0) {
    if(freq[prirotiy] == 0) {
      --prirotiy;
      s = std::stack<int>();
      continue;
    }
    if(q.front().first != prirotiy) rotate();
    else{
      --freq[prirotiy];
      if(s.empty()) {
        sum += q.front().second;
        s.push(q.front().second);
      }
      else check(s, q.front().second);
      q.pop();
    }
  }
}

int main (){
  std::cin >> N >> M;
  for(int i{0}; i<N; ++i) {
    int P, W;
    std::cin >> P >> W;
    q.push({P, W});
    freq[P] += 1;
  }
  solve();
  std::cout << sum;
  return 0;
}

사족

오랜만에 c++로 풀어서 문법이 약간씩 헷갈렸다. 처음에는 예제가 이해가 되지 않아서 힘들었다. 구현 자체는 쉽지만 생각을 자꾸 잘못하고, 디버깅 하느냐고 시간을 많이 쏟았다.