문제

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/12983

풀이

dp 문제입니다.
가장 기본적인 dp 문제인 계단 문제랑 비교해 보면 문자열t는 계단, 단어 조각인 strs는 한 번에 오를 수 있는 계단 수 라고 생각하면 됩니다.

1

 		int dp[] = new int[t.length()+1];
        dp[0] = 1;	

dp[i]는 문자열 t의 i번째 문자까지 도달하는 데 쓰인 단어 조각의 최소 개수입니다. 배열은 처음에 0으로 초기화 되어 있으니 구별하기 위해 dp[0]은 1으로 두었습니다. 정답에선 다시 뺄거에요.

2

 		for(int i = 0; i < t.length(); i++){
            if(dp[i] == 0){
                continue;
            }

문자열 t의 처음부터 하나씩 단어 조각을 대입해봅니다. dp[i]이 0이면 도달이 불가능한 구간이니 넘어갑니다.

3

            
            for(int j = 0; j < strs.length; j++){
                if(i + strs[j].length() > t.length()){ //단어 조각을 붙이면 문자열 길이를 넘어가는 경우
                    continue;
                }
                
                int k = 0;
                for(; k < strs[j].length(); k++){
                    if(t.charAt(i + k) != strs[j].charAt(k)){
                        break;
                    }
                }
                
                if(k != strs[j].length()){
                    continue;
                }

단순하게 하나씩 단어 조각을 대입해 문자열 t와 맞나 확인한 후

                dp[i+k] = dp[i+k] == 0 ? dp[i]+1 : Math.min(dp[i+k], dp[i] + 1);
            }
        }
        

dp[i+k]를 최소값으로 갱신해 줍니다. k는 단어 조각의 길이입니다.

4

        return dp[t.length()] == 0 ? -1 : dp[t.length()]-1;
    }		
 		

마지막으로 답을 리턴합니다. 배열의 마지막 부분이 0이라면 도달 불가능한 경우이니 -1을 리턴합니다.

---

전체 코드

class Solution {
    public int solution(String[] strs, String t) {
        int answer = 0;
        
        int dp[] = new int[t.length()+1];
        dp[0] = 1;
        for(int i = 0; i < t.length(); i++){
            if(dp[i] == 0){
                continue;
            }
            
            for(int j = 0; j < strs.length; j++){
                if(i + strs[j].length() > t.length()){
                    continue;
                }
                
                int k = 0;
                for(; k < strs[j].length(); k++){
                    if(t.charAt(i + k) != strs[j].charAt(k)){
                        break;
                    }
                }
                
                if(k != strs[j].length()){
                    continue;
                }
                
                dp[i+k] = dp[i+k] == 0 ? dp[i]+1 : Math.min(dp[i+k], dp[i] + 1);
            }
        }
        
        
        return dp[t.length()] == 0 ? -1 : dp[t.length()]-1;
    }
}