✓

태그:

22. 동적 계획법 2 CLASS 5 ESSENTIAL

지금까지 했던 질문과 그 결과를 저장하면 될 것 같아요…!!

풀이 비스무리한거 보기

주어진 문자열에 대해 부분 문자열을 계속 지정할 때 각 부분 문자열이 팰린드롬인지 각각 판별하는 문제입니다. 이 문제는 질문이 1e6개나 되기 때문에 각 경우에 대해 새로 팰린드롬인지 판별하면 시간이 매우 부족합니다. 따라서 DP를 이용하여 질문에 대한 결과와 그 서브-질문의 결과를 모두 저장해놓고 꺼내써야 합니다. 마치 피보나치 수를 여러 번 질문하는 문제처럼 말입니다. 2차원 배열에서 문자열의 시작 index와 끝 index를 index로 하는 원소에 결과를 저장해놓고, 값이 존재할 시 이를 참조하여 결과값을 빠르게 출력하면 됩니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-01-27 21:53:45
C	코드(Github) / 코드(백준)	2021-01-27 22:10:49	숏코드, 246바이트

---