[백준 1000] 알 수 없는 문장 - Java

백트래킹으로 접근하고자 생각했다.

• 1. 주어진 단어들을 무제한 사용할 수 있음으로, 문자열을 해석하는 각 순간에 같은 단어를 여러번 사용할 수 있다.

알고리즘

• 1. 주어진 인덱스부터 적용가능한 모든 단어들을 탐색한다.
• 2. 해석가능한 단어를 찾는다.
• 2-1. dp테이블에 현재까지의 비용을 계산 후, 최솟값으로 업데이트 한다.
• 2-2. 업데이트 시, 2 부터 다시 시작한다.
• 2-3. 업데이트가 안될 시, 이를 무시한다.

(2) 과정을 통해 특정 인덱스에서 실행 가능한 최소비용으로만 프로그램을 실행할 수 있도록 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    private static int minCost = Integer.MAX_VALUE;
    private static int dp[] = new int[51];

    public static void main(String[] args) throws IOException {
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        final String target = br.readLine();
        final int inputCount = Integer.parseInt(br.readLine());

        final List<String> words = new ArrayList<>();
        for (int i = 0; i < inputCount; i++) {
            final String input = br.readLine();
            if (input.isBlank()) {
                continue;
            }
            words.add(input);
        }

        getMine(words, 0, 0, target);

        //  백트래킹
        // 1. 시작 인덱스 0
        // 2. 해결가능한 단어 찾았을 시 다음 인덱스부터 단어 찾고 계산.
        // 3. 문장길이 + 1 이 현재 인덱스가 됐을 때, 종료
        //  3-1. 없는 놈 찾으면 스킵
        // 4. (3) 까지의 결과를 계속해서 최솟값 업데이트

        if (minCost == Integer.MAX_VALUE) {
            System.out.print(-1);
            return;
        }
        System.out.print(minCost);
    }

    public static void getMine(final List<String> words, final int currIndex, final int currCost, final String targetString) {
        if (currCost >= minCost) {
            return;
        }
        if (currIndex == targetString.length()) {
            minCost = Math.min(minCost, currCost);
            return;
        }
        for (final String word : words) {
            final int wordLength = word.length();
            if (wordLength + currIndex > targetString.length()) {
                continue;
            }
            final String separatedString = targetString.substring(currIndex, currIndex + wordLength);
            if (isEqual(separatedString, word)) {
                final int nextCost = currCost + getCost(separatedString, word);
                if (dp[wordLength + currIndex] > nextCost) {
                    dp[wordLength + currIndex] = nextCost;
                    getMine(words, currIndex + wordLength, nextCost, targetString);
                }
            }
        }
    }

    public static boolean isEqual(final String target, final String word) {
        final char[] targetArr = target.toCharArray();
        final char[] wordArr = word.toCharArray();
        Arrays.sort(targetArr);
        Arrays.sort(wordArr);
        return Arrays.equals(targetArr, wordArr);
    }

    public static int getCost(final String target, final String word) {
        int count = 0;
        for (int i = 0; i < word.length(); i++) {
            if (target.charAt(i) != word.charAt(i)) {
                count++;
            }
        }
        return count;
    }
}