[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

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 3111번: CENZURA  (0) 2018.01.22
[BOJ] 14891번: 톱니바퀴  (0) 2018.01.21
[BOJ] 2841번: GITARA  (0) 2018.01.20
[BOJ] 3986번: 좋은 단어  (0) 2018.01.20
[BOJ] 1196번: 잭 바우어  (0) 2018.01.19
[BOJ] 1543번: 문서 검색  (0) 2018.01.18
[BOJ] 9521번: PALETA  (0) 2018.01.17
  Comments
댓글 쓰기