배씨는 균형 잡힌 괄호 문자열을 미학적으로 매우 매력적으로 생각하지만, 특히 완벽하게 균형 잡힌 문자열이라고 부르는 문자열을 특히 좋아한다. 이 문자열은 ('로 시작하는 문자열 뒤에 길이가 같은 )' 문자열이 따르는 형태이다. 예를 들어 "(((())))"와 같은 문자열을 의미한다.

어느 날 헛간을 거니던 중, 배씨는 N \times N 크기의 바닥에 놓여진 말굽들을 발견한다. 각 말굽은 ( 또는 ) 중 하나의 모양으로 되어 있다. 이 바닥의 좌측 상단 모서리에서 시작해서, 배씨는 말굽을 따라 걸어가며 말굽을 주워 문자열을 만들고 싶어한다. 선택한 문자열이 완벽하게 균형 잡힌 문자열이 되도록 말굽을 선택해야 한다면, 배씨가 얻을 수 있는 가장 긴 완벽하게 균형 잡힌 문자열의 길이가 얼마인지 알아보자.

각 단계에서 배씨는 위, 아래, 왼쪽 또는 오른쪽으로 움직일 수 있다. 현 위치에 말굽이 있는 경우에만 이동할 수 있으며, 그렇게 할 경우 말굽을 집어 올려 해당 위치로 다시 돌아갈 수 없다 (이제 그 위치에는 말굽이 없기 때문이다). 배씨는 바닥의 좌측 상단 모서리에 있는 말굽을 집어 올리며 시작하여 완벽하게 균형 잡힌 문자열을 형성하는 일련의 말굽만을 집어 올리며, 따라서 바닥의 모든 말굽을 집어 올릴 수 없을 수도 있다.

#3798 upload 1회 done 1회 how_to_reg 1명

말굽 (Horseshoes) timer 1초 memory 128MB

문제 picture_in_picture_alt text_fields

예제1

출처

역링크 공식 문제집만

#3798

말굽 (Horseshoes) 1초 128MB

문제