[일반] 피린이 문제 도움좀 부탁 드립니다 ㅠ.

[기뉴(220.87)]

문제는   https://www.acmicpc.net/problem/16500

이 문제고 백트래킹으로 조합을 이용해서 푸는 알고리즘을 생각했는데 시간초과가 뜨네요... 

어떻게 해야 할까요?

이 문제를 dp로도 풀 수 있다 하는데 저는 dp로 어떻게 하는지 도저히 모르겠어서 백트래킹으로 했는데 고수분들 피드백 부탁드립니다...

제가 푼 코드는

http://boj.kr/7bb342dd712545d0a73cc15a35ec0449

이것 입니다.

[익명(223.39)]

그냥 dp - dc App

[기뉴(220.87)]

어떻게 dp로 접근하나요?

[익명(112.175)]

dfs에서 str이 s의 접두사가 안되면 컷해버린다고 생각해봐. 이 뒤로는 str에 뭘 붙여도 s를 못만드니까 당연한 생각임 그리고 str을 s의 접두사가 되게 만들었다고 하면 지금까지 str을 어떤 방식으로 만들었는지는 전혀 중요하지 않고 어떻게든 만들었다는 사실만 중요하다는 것도 알 수 있음 여기까지 이해했고 dp도 알고 있으면 못할수가 없다

[기뉴(220.87)]

혹시 소스코드 공유 가능하신가요? ㅠㅠㅠㅠㅠ 제가진짜 멍청해서 ㅠㅠㅠㅠ

[익명(112.175)]

님 코드 보고 적은건데 어떻게 코드가 있겠습니까

[기뉴(220.87)]

아... 그 dfs에서 if(str.charAt(0)!=s.charAt(0) return 추가 해도 시간초과 떠서요 ㅎㅎ... 알겠습니다

[익명(112.175)]

charAt이 아니고 s.substr써서 str전체랑 비교해야지...