22343. 괄호의 값 비교

 

22343번: 괄호의 값 비교

---

올바른 괄호 문자열 $A$, $B$가 주어졌을 때, $f[A]$와 $f[B]$를 비교하는 문제이다. 값을 비교하는 것이 목적이므로 값을 구하지 않아도 되지만, 다른 방법이 떠오르지 않아 그냥 구하기로 결정.

 

그런데 문제가 있다. 주어지는 문자열의 길이가 최대 300만이라 $f[A]$의 최댓값이 $2^{1500000}$이다. 로그를 적용해 보려 해도 $f[()] = 1$이라서 큰 애로사항이 있다. 1의 로그값은 0이기 때문이다.

---

마침 시간 제한이 4초이고, 메모리도 최대 1GB까지 쓸 수 있으므로 큰 수를 직접 구현해볼 수 있다.

안 되는데요?

아.. $2^{1500000}$을 문자열로 처리하려니 답이 없는 것이다. 자릿수 하나를 1바이트로 처리하기 때문이다.

 

따라서 한 자릿수를 1비트로 표현할 수 있는 큰 이진수를 구현해야 한다. cpp 사용자라면 비트마스크로 구현되는 ``std::vector<bool>``을 쓰면 된다. 파이썬이나 다른 언어는.. 화이팅 ^^

---

메모리 역대 최고값 같은데 ㅋㅋㅋ