LCS 5와 LCS 6을 둘 다 푼 상태에서 풀었는데도 꽤 힘들었습니다.
그냥 두 문제의 풀이를 합치면 되는 줄 알았는데, 그게 꽤 어렵더라고요.
푸는 과정에서 겪은 시행착오는 다음과 같습니다:
- 히르쉬버그를 재귀적으로 수행하는 과정에서 bitset<50000>을 계속 쓰면 시간 초과가 발생하므로, bitset의 길이를 조정해줘야 합니다.
- 그런데 그렇게 하면, cgiosy 님의 bitset::operator- 코드가 왜인지는 잘 모르겠지만 제대로 작동하지 않습니다.
그래서 비트셋을 직접 구현해서 풀었습니다.
- 를 알아내느라 폴리곤에 LCS 5 정해 코드, 제너레이터 (직접 짬), 체커 (직접 짬)을 넣어서 스트레스 테스트까지 돌려봤고, 문제를 본 지 3시간 만에 operator-이 문제라는 걸 알아냈습니다.
그 후 1시간 정도를 Bitset을 구현하는 데에 썼고, 결국 4시간 넘게 걸려서 풀었습니다. 꽤 뿌듯하네요. 특히 직접 구현한 비트셋이 매우 맘에 듭니다.