(28122) 아이템

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

단계별로 풀어보기

46단계(문자열 알고리즘 1) 7번째

 

 

 

2023 숭실콘 J번 문제이다. 에디토리얼에 잘 설명되어 있다. 이것보다 잘 설명할 방법을 모르겠다.

 

 

 

#include <iostream>
#include <map>
using namespace std;

struct Trie {
  int cnt= 0;
  Trie* next[2]= {nullptr, };
  ~Trie() { for(int i=0;i<2;i++)  if(next[i]!=nullptr)  delete next[i]; }
  
  void insert(const long n, int depth= 0){
    cnt++;
    
    if(depth==60)  return;
    
    if(next[n&1]==nullptr)  next[n&1]= new Trie();
    next[n&1]->insert(n>>1, depth+1);
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  Trie* root= new Trie();
  
  while(n--){
    long t;
    
    cin >> t;
    
    root->insert(t);
  }
  
  int res= 0, ans= 0;
  
  auto search= [&](auto self, Trie* now, int delta) -> int {
    if(now->cnt==delta)  return 0;
    
    if(now->next[0]==nullptr&&now->next[1]==nullptr){
      return (now->cnt)-delta;
    }else if(now->next[1]==nullptr){
      return self(self, now->next[0], delta+1)+1;
    }else if(now->next[0]==nullptr){
      return self(self, now->next[1], delta+1)+1;
    }else{
      int lres= self(self, now->next[0], max(0, delta-(now->next[1]->cnt))+1)+1;
      int rres= self(self, now->next[1], max(0, delta-(now->next[0]->cnt))+1)+1;
      
      return max(lres, rres);
    }
  };
  
  cout << search(search, root, 0);
  
  return 0;
}