플머12983 - DP, 문자열, 다시보기

import java.util.*;
class Solution {
    // t길이 + 1
    final int INF = 20001;
    HashSet<String> m = new HashSet<>();
    
    public int solution(String[] strs, String t) {
        int answer = 0;
        int maxL = 0;
        int N = t.length();
        
        for(String s : strs){
            maxL = Math.max(maxL, s.length());
            m.add(s);
        }
        
        int[] dp = new int[N+1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        
        for(int i = 1; i<=N; i++){
            for(int j = i-1; j >= Math.max(0, i-maxL); j--){
                if(dp[j] != INF && m.contains(t.substring(j,i))){
                    dp[i] = Math.min(dp[i], dp[j]+1);
                }
            }
        }

        return dp[N] == INF ? -1 : dp[N];
    }
}

정리

문자열 Target과 String이 들어있는 배열 Strs가 주어질때 strs에 들어있는 문자열을 활용해서 Target을 최소횟수로 구성할때 그 최소값을 구하고 구성할 수 없으면 -1을 출력하는문제

-> dp

 

풀이

이 문제의 핵심은 앞 문자열 + 뒷 문자열(strs에서 가장 긴 문자열의 길이까지만 봄)

인데 i <= N 까지 진행하고 j = i-1 에서 시작해서 max(i- maxL, 0) 까지 봄

 

문자열을 두 파트로 나눈다고 하면

t.substring(0, j) + t.substring(j, i) 로 나눌수 있으므로

dp [ j ] 가 유효하지 않은 값이 아닐때만 전파 가능함 

 

뒷부분 문자열이 strs의 원소라면 이거 1개를 더해서 dp[ i ] 를 완성 가능하므로

점화식은 전파 조건을 만족할 때

dp [ i ] = min(dp [ i ] , dp[ j ] + 1) 이 된다.

 

dp 크기는 최악의 경우 T의 한글자씩 떼는 것이기 때문에

T의 최대 길이 + 1 로 설정함.