상세 컨텐츠

본문 제목

[JAVA] 백준 10422번 괄호

알고리즘

by dajingjing 2022. 3. 28. 01:06

본문

https://www.acmicpc.net/problem/10422

 

10422번: 괄호

‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호

www.acmicpc.net

위 문제는 다이나믹 프로그래밍(DP) 방법으로 푸는 문제인데, 

헷갈렸던 부분이 있어서 적는다.

 

문자열 길이 L 이 주어지면, 주어진 길이 L에 해당하는 가능한 올바른 괄호의 경우의 수를 출력하는 문제이다.

 

예를들어 2가 주어지면 () 만 가능하므로 답은 1.

4가 주어지면 ()(), (()) 만 가능하므로 답은 2.

6이 주어지면 ()()(), ()(()), (())(), (()()), ((())) 만 가능하므로 답은 5.

홀수인 경우는 괄호의 짝이 반드시 하나가 남게 되므로 올바른 경우의 수는 0이다.

 

위 경우의 수를 잘 보면,

4인 경우는 첫번째 괄호 (가 2번째에서 끝나는 경우 1개, 4번쨰에서 끝나는 경우 1개가 있다.

6인 경우는 첫번째괄호 (가 두번째에서 끝나는 경우가 2개[ ()()() , ()(()) ],

첫번째괄호 (가 네번째에서 끝나는 경우가 1개 [ (())() ]

첫번째 괄호가 마지막 여섯번째에서 끝나는 경우가 2개다 [ (()()), ((())) ]

결론을 말하자면,

[첫번째 괄호가 끝나는 길이에서 가능한 경우의 수 x 나머지 자리수에 가능한 괄호의 수] 들의 합이 답이다.

첫번째 괄호가 끝나는 길이에서 가능한 경우의 수는, 첫번째괄호와 그 쌍을 이루는 괄호를 제외하고 안에 있는 가능한 괄호의 수이다.

(())() 인 경우, 첫번째 괄호와 쌍을 이루는 괄호는 4번째 괄호이며, 그 안에는 () 만 가능하다. [(12)()]

(1234) 인 경우는 첫번째 괄호와 쌍을 이루는 괄호는 6번째이며,그 안에는 길이가 4인 경우 가능한 괄호의 수가 나온다. ->[ (()()), ((())) ]

 

이 문제가 헷갈렸던 이유는.. 위 두 경우의 수를 곱한다고 생각했을때

중복된 데이터도 포함된다고 생각해서 헷갈렸다.

예를들어, () *()() 에다가 ()()*()도 포함되는거 아닌가? 헷갈렸는데,

처음 '(' 괄호와 그 쌍을 이루는 ')' 괄호를 제외한 길이에서 가능한 경우의 수를 곱해주는 거라서, 위 둘이 중복될 일이 없었다.

() * 1234(길이가 4인 경우의 수) 를 곱해준 다음에는 (12)*() 부분을 계산하기 때문이다.

 

 

 

 

관련글 더보기