백준 27192, Pick a Pair

개요

문제 링크
골드 3, String, Greedy
N개의 문자열로 N/2개의 pair를 형성할 때 pair의 prefix의 최소 길이의 최댓값

---

접근

1. 일단 문제의 핵심은 전체 pair들의 prefix를 생각할 필요가 없다는 것이다. Pair의 prefix의 최소 길이의 최댓값이라는 말라는 말이 엄청 헷갈릴텐데, 먼저 pair를 골라야 하고, 그 조합의 prefix 길이가 최대가 되도록한다고 천천히 생각하면 문제의 구조를 이해할 수 있다.

2. Pair를 고르는 것이 핵심인데, 아래 상황들을 천천히 읽어보자.

   1. Pair를 고를 조건, 즉 최소 prefix의 길이가 최대가 되도록 고르는 조건을 생각하는 과정이 상당히 그리디해서 Greedy를 추가했다.
   2. 사실 pair의 구성에는 최적의 pair가 항상 존재한다. 그게 무엇이고 어떻게 존재하냐? 하면 일단 예시를 보자.

       // ex1)
       a = AAAA
       b = AAAB
       c = AABB
       d = ABBB
       // answer = 1

      a의 최적 pair는 b가 되고, c의 최적 pair는 d가 된다. 남아있는 문자열 중 가장 prefix의 길이가 긴 문자열을 상대 pair로 고르는 것이 이득이라는 것인데, 아래 예시를 더 보자.

       // ex2)
       a = AAAA
       b = AAAB
       c = AABC
       d = AABD
       // answer = 3

      a의 pair로 b가 아닌 c를 고른다면? c와 d의 prefix길이인 3이 방해를 받고, (a,c) = 2, (b,d) = 2로 prefix길이의 최댓값은 2가 된다.

3. 일단 여기까지는 예시고, 그럼 각 문자열마다 prefix의 길이가 가장 긴 문자열을 일단 고르고 봐야 한다는 건데, 이게 진짜 최적일까? 혹시 다른 선택지를 선택하면서 원래 상대가 더 최적의 선택을 할 수 있지 않나? 하는 생각을 할 수 있다.

   1. 다시 말해 (a,b), (c,d)의 pair가 있을 때, (a,c), (b,d)의 pair를 형성함으로써 a pair의 prefix의 길이는 줄어들지라도 (b,d)의 prefix 길이는 (c,d)보다 늘어나서 최소 prefix가 증가하지 않을까? 하는 것이다.
   2. 만약 a,b,c,d가 공통된 prefix를 갖지 않는 아래의 상황이라면 최소 prefix는 감소한다. 여기까지는 쉽게 생각할 수 있다.

       // ex3)
       a = AAAA
       b = AAAB
       c = BBBB
       d = BBBC
       // answer=3

   3. 하지만 위에서 본 2번 예시를 다시 보자. 2번 예시는 4개 문자열의 공통 prefix가 있음에도 (a,c), (b,d) 선택에서 최소 prefix가 감소한다. 개별 최적 선택지가 b는 a, c는 d, d는 c가 되기 때문이다. 즉 pair를 형성하는 데에 겹치는 부분이 없어서 개별의 최적선택이 전체의 최적이 된다.
   4. 그럼 마지막으로 1번 예시를 보자. 개별 최적 선택지는 b는 a (prefix=3), c는 a,b (prefix=2), d는 a,b,c (prefix=1) 가 된다. 겹치는 부분이 생겨버렸다.
      1. 그럼 a에서는 어떤 문자열을 선택해야 할까? 우선 앞서 b를 선택하는 것이 최적이라 했는데, 이유는 (a,d) pair를 만들어도 기존의 (a,b), (c,d)의 최소 prefix인 1을 벗어날 수 없기 때문이다.
      2. c가 a또는 b의 선택을 받을 수는 없을까? 이때는 a,b 중 하나는 무조건 d를 선택해야 하는데, 이때도 어차피 최소 prefix인 1을 벗어날 수 없다.
      3. 만약 d pair의 prefix가 1보다 커지는 상황이라면? 그러면 d의 최적 선택지 구성이 달라질 것이고 최적 선택을 하지 않은 상황이 된다. 전제가 잘못되었다.
   5. 핵심은 최소 prefix를 가지는 pair를 구성하는 원소가 존재하고, 그 원소는 다른 어떤 원소와 pair를 형성해도 최소 prefix를 가진다는 것이다. 아예 첫 자리부터 다른 3번 예시, 앞의 몇 개는 같지만 결국 뒤로 가면 더 손해가 되어버리는 2번 예시, 앞이 모두 같지만 결국 그게 최소인 1번 예시를 기준으로 가닥을 잡아보면 된다.

4. 여기까지 쭉 읽고 나면 결국 최적 선택지는 prefix의 길이가 긴 문자열이고, 인접한 문자열의 prefix의 길이가 최대가 되도록 배치하는 것은 사전순 배열이 됨을 알 수 있다. 그래서 코드 자체는 매우 단순하다. 그냥 정렬하고, 2개씩 prefix의 길이를 보면서 최솟값을 찾아주면 된다.

좀 엄밀하게 가다보니 설명을 너무 어렵게 해버렸고 틀린 부분도 좀 있는 것 같은데, 핵심은 부분의 최적이 전체의 최적이라는 것이고, 나머지는 문자열에 익숙하다면 크게 어렵지 않을 것이다.

---

Pseudo code

sort(string)
for (i=0;i<n;i+=2)
    ans = min(prefix(s[i],s[i+1]))

---

Source code

#include <bits/stdc++.h>
using namespace std;

using str=string;

int pre(str &a,str &b) {
    int i=0,m=a.size();
    while(a[i]==b[i]&&i<m) i++;
    return i;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n;
    cin>>n;
    str s[n];
    for (auto &x:s) cin>>x;
    sort(s,s+n);
    int m=s[0].size();
    for (int i=0;i<n;i+=2)
        m=min(m,pre(s[i],s[i+1]));
    cout<<m;
}