BOJ 3012 올바른 괄호 문자열

정상 회담 2 문제를 풀던 중 백준님의 풀이에 이 문제의 풀이가 올바른 괄호 문자열을 구하는 문제의 풀이와 비슷하다고 나와있어서 풀어보고 다시 정상 회담 2를 풀어보려고 한다. 이 문제는 내가 예전에 백준님의 풀이를 보고 시도했던 것인데 백준님의 코드를 너무 그대로 따라해서 내가 직접 짜보려고 남겨뒀던 것 같다.

일단 다시 봐도 풀이가 생각이 안나서 점화식 정의와 풀이를 봤다.
d[i][j]=i~j문자열을 이용해서 만들 수 있는 올바른 괄호 문자열의 개수
그리고 i번째의 왼쪽 괄호와 짝이 맞는 k번째의 오른쪽 괄호가 있을 때,
d[i][j]는 d[i+1][k-1]*d[k+1][j]로 표현할 수 있다. 즉 i번째의 왼쪽 괄호와 짝이 맞는 모든 k번째의 오른쪽 괄호의 경우들로 전체 경우를 표현할 수(나눌 수) 있는 것이다.
이 문제가 정상회담 문제와 비슷하다는 것이 정상회담 문제도 1번 사람이 누구와 악수를 하는지로 전체 경우를 나눌 수 있었고 1번 사람이 누구와 악수를 할 경우 악수가 교차되면 안되므로 그 악수 왼쪽 편과 오른쪽 편의 곱으로 경우의 수를 구할 수 있었다.

문제 접근 방법만 놓고보면 똑같다고 할 수 있겠다. 왜 다양한 문제를 많이 풀어봐야 하는지를 어렴풋이 알 것 같기도 하다.

문제를 푸는데 계속 틀려서 백준님 코드와 비교해봤더니... 나는 별 필요 없을 거라고 생각한 부분이 바로 틀리는 이유였다. 문제의 출력 조건에 보면 올바른 괄호 문자열의 개수가 다섯 자리를 넘으면 마지막 다섯 자리만 출력하라고 되어있다. 이 부분을 처리하기 위해 MOD=100000로 놓고 %연산을 계속 해주는데, 점화식에 곱하기가 있으므로 int형 범위를 넘을 수 있기에 long long을 사용해야 한다. 그리고 하나 더 가장 중요한 부분 MOD로 중간 중간 나눠줘도 어차피 답은 각 곱과 합으로만 구성되어 있기 때문에 최종 답의 마지막 다섯 자리 수만 나오게 될 것 같지만... 반은 맞고 반은 틀리다고 할 수 있다. 왜냐하면 만약 답이 100000123인 경우 마지막 다섯 자리는 00123인데, 123을 출력하기 때문이다. 그래서 중간에 다섯 자리가 넘는지 체크하고 만약 넘었다면 printf("%05lld"를 이용해서 출력해줘야 한다.

출처 : 백준님 강의, 강의 자료