백준 20051번 Zagrade

http://icpc.me/20051

20051번: Zagrade

문제

인터랙티브 문제입니다.

길이가 짝수인 정수 $N$이고 여는 괄호( '(' )와 닫는 괄호( '(' )의 개수가 같은 문자열이 있을 때, 

? s e 쿼리로 [s, e] 구간의 문자열이 올바른 괄호 문자열인지 검사할 수 있습니다.

최대 $Q$번의 쿼리로 전체 문자열을 알아내는 문제입니다.

 

풀이

서브테스크 1, 2)

$Q = \frac{N^2}{4}$인 경우입니다.

사실 생각해보진 않았습니다

길이가 홀수인 부분 문자열은 올바른 괄호 문자열이 될 수 없으니 검사할 필요가 없습니다.

길이가 짝수인 부분 문자열 $(\frac{N}{2})^2$개를 모두 검사하는 풀이를 의도했을 것 같습니다.

서브테스크 3, 4의 풀이로도 풀 수 있습니다.

 

서브테스크 3)

$Q = N - 1$이고 전체 문자열이 올바른 괄호 문자열인 경우입니다.

올바른 괄호 문자열이므로 스택을 이용하면 모든 괄호의 짝을 맞출 수 있습니다.

짝이 맞는다면 시작점과 끝점의 문자를 알 수 있으므로,

끝점이 2 ~ $N$인 경우를 모두 검사하면 전체 문자열을 알 수 있습니다.

 

코드

 

서브테스크 4)

서브테스크 3에서 전체 문자열이 올바른 괄호 문자열이 아닌 경우도 생각해야 합니다.

서브테스크 3과 같은 방식으로 쿼리를 주었을 때 결과가 모두 0인 경우를 생각해 봅시다.

여는 괄호와 닫는 괄호의 수가 같으니 이 경우에는 문자열이 반드시 )))...)(...((( 의 형태입니다. 

만약 1인 결과도 있지만, 전체 문자열이 올바른 괄호 문자열이 아닌 경우는 어떨까요?

서브테스크 3의 방식대로 스택에 넣고 빼기를 반복하면 $N - 1$개의 쿼리를 모두 사용한 뒤 스택에는 짝을 맞추지 못한 위치들만 남게 됩니다.

스택에 남은 위치들만 쭉 이은 문자열을 $A$라고 하면, $A$의 모든 부분 문자열은 올바른 부분 문자열이 아니라는 것을 알 수 있습니다.

따라서 앞서 살펴본 것처럼 $A$는 ))...)(...(( 의 형태입니다.

즉, 스택에 넣고 빼기를 반복하며 짝이 맞는 위치들은 바로 문자를 확정하고, 모든 쿼리를 수행한 이후 $A$를 위와 같은 형태로 정해주면 답을 구할 수 있습니다.

 

코드

 

사족

처음으로 푼 인터랙티브 문제였는데, 정말 재밌게 풀었습니다.

이제 코포에 인터랙티브 나와도 풀 수 있을 것 같습니다.