시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 1481 | 559 | 402 | 40.812% |
극지 연구소에서 연구 중인 협이는 새로운 북극곰의 특성을 발견했다. 그것은 바로 북극곰이 $O$와 $X$를 보면 $()$와 $)($로 찢어버린다는 것이다.
협이는 이러한 북극곰의 특성을 이용하여 길이 $N$의 괄호 문자열 $S$를 만들고자 한다. 북극곰은 낮에 활동을 하기 때문에 낮에 돌아다니는 것은 위험하다. 때문에 협이는 매일 밤마다 활동할 수 있다. 밤에 협이는 문자열이 있으면 그 위에 $O$ 또는 $X$를 원하는 만큼 놓을 수 있다. 그러면 낮에 북극곰이 와서 문자들을 모두 찢어 놓는다.
예를 들어 이미 문자열 $()()$가 있다고 생각해보자. 밤에 문자를 $(O)X(O)$ 다음과 같이 놓아둔다면 하루가 지나 $(()))((())$ 와 같은 문자열이 된다.
이때 원하는 문자열을 만들려면 최소 며칠이 걸리는지 계산해보자.
입력은 아래와 같이 주어진다.
$N$
$S$
원하는 문자열을 만들기 위해 걸리는 최소 일수를 구하라.
원하는 문자열을 만들 수 없다면 -1
을 출력한다.
(
' 또는 ')
'로 이루어져 있다.6 ()()()
1
10 (()))((())
2
3 (()
-1
University > 연세대학교 > 2022 연세대학교 프로그래밍 경진대회 D번