[ICPC] 백준 23248 - Treasure Hunter

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

 

밑에 적은 풀이는 추가된 데이터로 TLE를 받을 예정이다. 빠른 풀이에 대해선 여기를 참고하라.

 

https://nicotina04.tistory.com/276

LIS와 multiset

 

힌트

각종 태그에 겁먹지 말자. 이 문제는 set으로 풀 수 있으며 본인도 본 대회에서 set으로 AC를 받았다.

 

로봇이 갈 수 있는 방향에 근거하여 X들을 서로 이어보자. 무언가를 깨달을 수 있다.

풀이

X들의 좌표를 정렬했을 때 처음에 나타나는 X를 시작으로 로봇이 한 번에 갈 수 있는 X끼리 연결해보자. 문제 지문에서는 다음과 같이 연결될 것이다.

 

 

물론 이렇게 할 수도 있다.

 

 

이렇게 여러 테스트 케이스를 생각하여 X들을 잇다 보면 이 사실을 발견할 수 있다.

 

오름차순으로 나타난 X들을 로봇의 이동 규칙을 지키면서 최대한 길게 연결하면 여러 경우가 생길 수 있어도 필요한 로봇의 개수는 똑같으며 이것이 최적해이다.

 

그러면 우리는 중간 원소를 빠르게 지울 수 있는 자료구조를 통해 남아 있는 X 중 첫 번째 좌표부터 순회하여 이동 조건을 만족하는 X들을 제거해나가면 답을 구할 수 있다.

 

중간 원소를 $O(\log N)$에 삭제하고 그 와중에도 오름차순을 유지할 수 있는 set을 사용하면 쉽게 구현할 수 있다.

 

그렇게 set을 완전히 비울 때까지 로봇을 호출한 횟수가 정답이 된다.

 

참고로 한 번 정렬을 수행하면 오름차순이 유지되는 상태이므로 std::set 대신 연결 리스트를 이용하면 $O(1)$에 중간 원소를 삭제할 수 있으니 std::list를 사용해보자. 아직 본인은 시도해보지 않았다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;
using namespace __gnu_cxx;
using ll = long long;
using pii = pair<int, int>;

int m, n, k;
set<pii> st;
int ans;

void solve()
{
  cin >> m >> n >> k;

  for (int i = 0; i < k; ++i)
  {
    int a, b;
    cin >> a >> b;
    st.insert({a, b});
  }

  while (st.size())
  {
    ++ans;
    auto x = *st.begin();
    st.erase(st.begin());

    auto it = st.begin();
    while (it != st.end())
    {
      if (x.first <= it->first && x.second <= it->second)
      {
        x = *it;
        st.erase(it++);
      }
      else
      {
        ++it;
      }
    }
  }

  cout << ans << '\n';
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  solve();
}

제출 기록(ICPC Korea 2021 예선)

해당 문제는 K번으로 출제되었다.

제출 기록(백준)

백준의 제출 결과로 보아 대회 중 가장 느린 풀이로 추정된다.