프로그래머스 단어퍼즐 c++

처음에는 완전 탐색으로 구현할까 생각했지만, 테스트케이스를 보고 dp로 풀어야겠다고 생각했다. 점화식은 다음과 같다. dp[i] = i번째 string까지 만들 수 있는 최소비용 d[i] ~ d[t.size()-1] 까지 순회를 돌면서 각각의 strs 원소가 들어가는지 확인하고, 들어가면 dp[i] = min(dp[place-1]+1, dp[i])로 최소비용을 업데이트해준다. 그리고 첫번째 값의 경우에는 dp[place-1] 값이 존재하지 않는다. 이럴때는 1로 초기화해준다. 왜냐하면 banana 에서 b라면 최초의 경우라 1로 값이 설정되기 때문이다. 이렇게 dp로 풀어야한다. 처음에 이렇게 풀었지만, 효율성조건을 만족하지 못했다. 이는 c++ string의 시간이 오래걸리기 때문이다. 처음에는 주석처..

2023.09.29