백준 16500번 문자열 판별

문제

알파벳 소문자로 이루어진 문자열 S와 단어 목록 A가 주어졌을 때, S를 A에 포함된 문자열을 한 개 이상 공백없이 붙여서 만들 수 있는지 없는지 구하는 프로그램을 작성하시오. A에 포함된 단어를 여러 번 사용할 수 있다.

문제풀이

사용한 알고리즘 : DP

(1) 코드 6

 a~z 26개의 단어 중 어떤 것으로 끝나는지 구분하여 저장합니다.

 'S[x] : 'x로 끝나는 단어' 라고 설정한 벡터를 하나 만들었습니다.

(2) 코드 7

 'dp[k] : k~끝까지 만들 수 있는지 여부'라고 설정한 dp를 bool 형식으로 만들어줍니다.

 우리 목표는 문자열 S 의 뒤에서부터 주어진 목록 A의 단어들을 채워 나가는 것입니다.

 문자열 S의 첫번째 단어까지 채워지면 1을 출력할 것이고, 아니면 0을 출력할것입니다. 

(3) 코드 20~40

 문자열 S의 맨 뒤 글자부터 탐색을 할 것입니다.

 i번째를 탐색할 시, i+1 까지 채워졌다면 i번째에 들어갈 수 있는 단어를 넣어볼 것입니다.

 따라서 문자열 S 길이 바로 뒷 글자는 채워졌다고 생각하고 탐색을 시작합니다.

 i번째 탐색시, S의 i번째와 같은 글자로 끝나는 단어들을 봅니다.

 각 단어가 들어갈 수 있는지 확인하고, 

 들어갈 수 있다면 단어가 들어간 길이만큼 앞의 dp값을 최신화 해줍니다.

(4) 코드 42~43

 dp[0]=true 이면 0에서~끝까지 채워질 수 있다는 것입니다.

 이를 생각하여 답을 출력해줍니다.