tipstown 코드그라운드 4/10 11시 59분 종료한 후 질문을 드립니다~

100,100,43점을 획득했는데.. 아직 실력이 모지라지만 모르는 것은 배우고 가고 싶어서 백준 게시판에 질문드려봅니다~ (혹여나 문제가 된다면 삭제하겠습니다. 예선은 종료되었습니다.)

["ca","da","d","a"] "cadada"  = t

n개의 문자열 조합으로, cadada를 만들 수 있는 최소 횟수는?

ca d a d a 로도 만들 수 있지만, 5개..

ca + da + da 로 3개.. (이것이 정답)

문자열 조각는 무한개수가 존재한다, 무한번 사용할 수 있다. ex) bababababa 이런식으로 사용 가능

문자열 조각의 길이는 1~5  맞춰야할 문자열 t는 1~20000

못구하면, -1 출력

백트래킹으로 시도를 해봤는데 시간초과가 나고 43점을 획득했습니다..

문자열 조각을 무한번 사용할 수 있기 때문인 것 같은데.. 느낌은 그리디로 해야할 것 같은데..

아래 저의 허접한 코드를 적어봤구요! bfs나 그리디 정도가 생각은 났는데 전혀 못건드릴 것 같아서

완전 탐색..백트래킹으로 풀어봤습니다. 조언 혹은 c,c++ 상관없이 약간의 solution 코드를 작성해주신다면

너무나도 감사할 것 같습니다! 

(sorting 이나 첫 시작 char 검사는 사실 의미 있을지 모르겠는데, 마지막 시간은 얼마 남지도 않았고 어떻게든 점수좀 올려보려고 했으나 실패..)