다이나믹프로그래밍

오늘은 백준 3012번 문제를 풀어보려고 한다. 이 문제는 07/08 크로아티아 정보올림피아드 기출문제이다. https://www.acmicpc.net/problem/3012 3012번: 올바른 괄호 문자열 예제 1의 경우 다음이 가능하다. ({([()])}), ()([()]{}), ([([])]{}) www.acmicpc.net 크로아티아 정보올림피아드 기출 문제여서 그런지 문제에 대한 아이디어가 쉽게 떠오르지는 않았던 것 같다. (난이도도 심지어 플레티넘 3 ㄷㄷ...) 처음에는 ? 각각에 들어갈 수 있는 문자 "{", "[", "(" 등을 찾아서 경우의 수를 생각해 주어야 하나? 라고도 떠올려 봤는데 너무 생각해 주어야 할 케이스가 많았고 이 방법은 맞지 않다는 것을 깨달았다. 결국 DP를 통해 한..

오늘 설명할 문제는 백준 10422번 문제이다. https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 ST도 올바른 괄호 문자열이다. (()())()은 올바른 괄호 문자열이지만 (()은 올바른 괄호 문자열이 아니다. 괄호 문자열이 주어졌을 때 올바른 괄호 문자열인지 확인하는 방법은 여러 www.acmicpc.net 이 문제는 동적 프로그래밍을 사용해서 푸는 문제이다. 아이디어를 알고 나면 되게 쉽지만, ..