BOJ 16890 - 창업

BOJ 16890 - 창업

개인적으로 상당히 생각하기 까다로운 문제이다.

코포 문제 라고 한다. 레이팅은 1800 이다.

이렇게 보면 Solved.ac Gold 2가 코포에서 레이팅이 1800정도라는 건데, 확실히 아이디어성 문제들이 훨씬 더 어렵게 느껴지는 것이 있다.

여러번 틀리고 나서야 풀 수 있었다.

우선, $\vert A \vert=N$ 이라면 선공은 $\left\lfloor \dfrac{N+1}{2} \right\rfloor$개를 쓸 수 있고, 후공은 $\left\lfloor \dfrac{N}{2} \right\rfloor$ 개를 쓸 수 있다.

만약 $N=1$ 이라면 따로 예외처리 해주자.

선공은 항상 가진 문자열 중 작은 것 순으로 $\left\lfloor \dfrac{N+1}{2} \right\rfloor$ 개를 써야하고, 후공은 큰 것 순으로 $\left\lfloor \dfrac{N}{2} \right\rfloor$개를 써야함은 쉽게 보일 수 있다.

단순히 생각할 수 있는 것은 항상 선공, 후공 모두 자신이 가진 것 중 가장 작은것과 가장 큰것을 계속 앞에 붙여나가는 것인데, 이는 대부분의 케이스를 통과하지만 예외가 있다.

선공이 가진 가장 작은 것이 후공이 가진 가장 큰 것 으로 사전순 이상일 때를 고려한다.

이 땐, 선공이 가장 작은것을 앞에 붙여도 최적이 아닐 수 있다.

이 경우엔 자신이 두어야 할 것 중 가장 큰 것을 남은 위치 중 가장 뒤에 붙인다.

왜냐면 자신이 가진 가장 작은것을 자신이 제일 앞에 두지 않아도, 상대방이 언젠간 그것 이하의 것을 채워줄 것이기 때문이다.

void solve() {  
   string a, b, c;  
   cin >> a >> b;  
   int n = sz(a);  
   c = string(n, '?');  
   sort(all(a));  
   sort(all(b), greater<>());  
  
   int a_use = (n + 1) / 2;  
   int b_used = n / 2;  
   deque<char> A, B;  
   for (int i = 0; i < a_use; i++) A.pb(a[i]);  
   for (int i = 0; i < b_used; i++) B.push_front(b[i]);  
  
   if (b_used == 0) {  
      cout << A[0];  
      return;  
   }  
   for (int front = 0, back = n - 1, turn = 0; turn < n; turn++) {  
      if (turn % 2 == 0) {  
         if (A.front() >= B.back()) {  
            c[back--] = A.back();  
            A.pop_back();  
         } else {  
            c[front++] = A.front();  
            A.pop_front();  
         }  
      } else {  
         if (A.front() >= B.back()) {  
            c[back--] = B.front();  
            B.pop_front();  
         } else {  
            c[front++] = B.back();  
            B.pop_back();  
         }  
      }  
   }  
   cout << c;  
}