[Programmers] 단어 퍼즐

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12983

코딩테스트 연습 - 단어 퍼즐

DP를 이용하는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 점화식을 cache[t의 인덱스] = min(cache[t의 인덱스], cache[t의 인덱스 - 원소 길이] + 1)로 설정해줍니다.

1.1 여기서 cache[t의 인덱스]란 t의 인덱스까지의 부분 문자열을 뽑았을 때 단어 조각들의 최소 숫자입니다.

2. 이중 반복문을 통해 위 점화식을 구해줍니다.

3. cache[t의 길이]가 INF라면 문자열을 단어 조각들로 형성 못하므로 -1을 반환해주고, 그 외 케이스는 cache[t의 길이]를 반환해줍니다.

3.1 cache[t의 길이] = t의 길이까지의 부분 문자열을 이루는 단어 조각들의 최소 숫자 = t를 이루는 단어 조각들의 최소 숫자

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~