문제 링크입니다: https://www.acmicpc.net/problem/16500
16500번: 문자열 판별
첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 ��
www.acmicpc.net
오랜만에 풀어보는 DP 문제였습니다.
가지치기만 적당히 해준다면 쉽게 풀 수 있는 문제입니다.
알고리즘은 아래와 같습니다.
1. S 문자열 idx번째 인덱스부터의 부분문자열이 A에 포함된 단어 중 하나와 일치하는지를 확인합니다.
2. 일치한다면 (idx + 부분문자열의 길이) 번째부터의 부분문자열이 또 A에 포함된 단어 중 하나와 일치하는지를 확인합니다.
3. 위 과정을 반복하다가 S 문자열의 끝까지 도달한다면 A의 단어들로 S를 공백없이 구성할 수 있기 때문에 1 즉, true를 출력해줍니다.
* 주의할 점은 S 문자열의 길이를 초과하면 안된다는 점입니다!
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 1949번 우수 마을 (0) | 2020.05.18 |
|---|---|
| 백준 15829번 Hashing (0) | 2020.05.18 |
| 백준 1059번 수2 (0) | 2020.05.08 |
| 백준 2592번 대표값 (0) | 2020.05.03 |
| 백준 2581번 소수 (0) | 2020.05.03 |