문제 링크입니다: https://www.acmicpc.net/problem/2186
2186번: 문자판
첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다.
www.acmicpc.net
DFS + DP 문제였습니다.
처음에는 DFS 알고리즘만 적용했는데 시간초과가 발생했습니다.
(최대 100 * 100 보드판에 최대 80 길이의 문자열을 찾아야하고 visited 배열을 사용할 수 없기 때문에 당연히 TLE가 발생합니다.)
따라서, 각 칸과 목표 문자열의 인덱스를 기준으로 캐싱하여 DP를 적용하면 시간초과를 방지할 수 있습니다.
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 2957번 이진 탐색 트리 (0) | 2019.10.08 |
|---|---|
| 백준 2933번 미네랄 (0) | 2019.10.07 |
| 백준 5635번 생일 (2) | 2019.10.02 |
| 백준 6118번 숨바꼭질 (0) | 2019.09.29 |
| 백준 1516번 게임 개발 (0) | 2019.09.29 |