2271 - 암호화 알고리즘의 약점

문제 링크

---

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

문제 요약

---

자연수로 이루어진 크기 \(N\)인 배열 \(A\)가 주어진다. 이 때 \(1\leq P\ \lt\ Q\ \lt\ R\ \lt\ S\ \leq\ N\)을 만족하는 \(P\), \(Q\), \(R\), \(S\)에 대해 아래 두가지 수식이 만족하는 경우가 있는지 찾는 문제다.

1. \(A[Q]\ \lt\ A[S]\ \lt\  A[P]\ \lt\ A[R]\)

2. \(A[Q]\ \gt\ A[S]\ \gt\  A[P]\ \gt\ A[R]\)

문제 풀이

---

우선 2번 경우는 생각하지 말고 1번 경우만 생각해 보도록 하자. \(i\lt j\) 인 임의의 \(i\), \(j\)를 선택했다고 하자. 만약 \(A[i] \lt A[j]\)를 만족을 한다면 각각의 \(i\), \(j\)는 각각 \(Q\), \(S\) 후보가 될 수 있다. 그렇다면 남은 문제는 가능한 \(P\), \(R\)이 있는지 확인하는 문제로 축소가 된다. 우리는 모든 경우를 세는 것이 아니라 약점이 있는지 없는지만 확인하면 되기 때문에 이 문제를 간단하게 해결할 수 있다.

우선 약점이 존재하도록 하는 \(A[R]\)들의 후보를 생각해보자. \(R\)은 \(Q\)보다 크고 \(S\)보다는 작기 때문에 우리가 선택한 \(i\)와 \(j\)사이에 있을것이 자명하다. 이 때 \(A[P]\)값이 존재하기 위해서는 \(A[R]\)이 크면 클수록 유리하다는 사실또한 자명하다. 그렇다면 \(A[R]\)값을 \(max(A[i + 1]...A[j - 1])\)로 가정을 해도 괜찮다는 얘기가 된다.

만약 \(A[j]\)보다 큰 \(max(A[i + 1]...A[j - 1])\)값이 존재한다면 \(A[R]\)값이 존재한다는 뜻이 되고 마지막으로 가능성이 있는 \(A[P]\)만 찾으면 1번 경우의 약점을 찾게 되는 것이다. \(A[P]\)의 값은 \(A[1]...A[i - 1]\) 중에 \(A[R]\)에서 가장 가까운 작은값이 되는것이 유리하다는 것을 알 수 있다. 이를 찾는것은 \(set\)을 통해 쉽게 찾을 수 있다.

이렇게 모든 \(i\), \(j\)에 대해서 가능한 경우가 존재하는지 판단을 하면 되고 이 때 시간복잡도는 \(O(N^2logN)\)이 된다. 2번의 경우는 별도로 설명하진 않았는데 부호가 정 반대인 경우이므로 원래의 배열을 뒤집은 다음에 1번의 경우가 존재하는지 판단하는 것과 동일한 방법으로 2번의 경우를 찾을 수 있다.

소스 코드

---

#include <stdio.h>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

int t, n;

bool hasWeakness(const vector<int>& vi) {
  set<int> s;
  for (int i = 0 ; i < n ; ++i) {
    int mmax = 0;
    for (int j = i + 1 ; j < n ; ++j) {
      if (vi[i] < vi[j] && vi[j] < mmax) {
        auto it = s.upper_bound(-mmax);
        if (it != s.end() && vi[j] < -(*it)) {
          return true;
        }
      }
      mmax = max(mmax, vi[j]);
    }
    s.insert(-vi[i]);
  }
  return false;
}

int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    vector<int> vi(n);
    for (int i = 0 ; i < n ; ++i) {
      scanf("%d", &vi[i]);
    }
    bool ans = hasWeakness(vi) || hasWeakness(vector<int>(vi.rbegin(), vi.rend()));
    printf("%s\n", ans ? "Yes" : "No");
  }
}