[BOJ] 3986번: 좋은 단어

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

비슷한 유형의 문제를 상황에 따라 Dynamic Programming으로 풀기도 하는데 (http://baaaaaaaaaaaaaaaaaaaaaaarkingdog.tistory.com/125) 이 문제는 N의 크기에서 알 수 있듯이 Dynamic Programming으로 푸는 것이 불가능합니다. 대신 stack을 활용해서 바로바로 매칭시켜주는 방식으로 풀어낼 수 있습니다.

이 방식이 왜 되는지 궁금하다면 word의 길이가 2일 때 stack에 남은 것이 없으면 가능하다는 것을 먼저 보인 후, 귀납법으로 증명할 수 있을 것으로 보입니다.

https://github.com/blisstoner/BOJ/blob/master/3986.cpp