https://www.acmicpc.net/problem/10422
위 문제는 다이나믹 프로그래밍(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)*() 부분을 계산하기 때문이다.
[JAVA] 백준 1413번 박스 안의 열쇠 (0) | 2022.04.08 |
---|---|
[JAVA] 백준 10564번 팔굽혀펴기 (0) | 2022.04.07 |
[JAVA] 백준 3012번 올바른 괄호 문자열 (0) | 2022.04.06 |
[JAVA] 백준 14238번 출근 기록 (0) | 2022.03.31 |
[JAVA] 백준 11049번 행렬 곱셈 순서 (0) | 2022.03.30 |