[백준 / BOJ] 1099 알 수 없는 문장 (Java)

문제

출처 : https://www.acmicpc.net/problem/1099

1099번: 알 수 없는 문장

몇개의 단어로 이루어진, 길이가 최대 50인 문장이 있다.

이 문장은 특이하게, 문장을 이루는 단어의 알파벳이 섞여있어도 된다.

 

예를들어,

neotowheret

는

one

two

three

there

중 3개의 단어를 사용해서 만들수있다.

 

neo - > one

tow -> two

heret -> three

heret -> there

 

단어를 해석할때, 각 단어의 바뀐 알파벳의 idx에 따라서, 해석하는 비용이 증가한다.

예를들어, neo와 one의 경우 3가지 알파벳의 위치가 모두 다르므로, 3의 비용이 소모된다.

 

최대길이 50의 문장, 단어의 수 N(N <= 50), N개의 단어가 주어질때, 문장을 해석하는 최소비용을 구하는문제다.

단, 해석하지못한다면 -1을 출력한다.

---

풀이

다이나믹 프로그래밍으로 푸는 문제였다.

문제 해석부터, 풀이까지 오랜시간이 걸린 문제다.

 

해석할때,  각 단어의 알파벳순서를 임의로 섞을수있다는 부분을 유의해야 했는데, 이 의미가 각 단어의 알파벳을 붙여놓지 않아도 된다는 의미는 아니였다. 즉, 단어를 이루는 알파벳의 순서는 상관없지만,  항상 해당 단어의 알파벳이 서로 연속적으로 있어야한다. (이걸 늦게 알아서 해맸었다.)

 

예를들어, 문장 neno 를 one이라는 단어를 갖고 해석한다고 가정해보자.

위 문장에서 one이라는 단어를 찾기위해선, idx = 3, idx = 2, idx = 1을 사용해야한다. 단어를 이루는 알파벳이 같다고해서 idx = 0 idx = 1 idx = 3 이런식으로 사용하지 못한다는 의미다.

 

로직

임의의 문장 S가 있다고 가정하자.

위 해석을 토대로 문장을 해석하기위한 2가지 조건을 생각할수있었다.

 

1. 문장은 항상 앞에서부터(혹은 뒤에서부터) 연속적으로 해석되어야한다.

2. 1번 조건에 따라, dp식을 다음과 같이 생각할수있다.

- dp[idx] = 문장의 idx까지 해석하기 위해 필요한 비용의 최솟값

 

dp식

문장의 몇번째 idx부터 끊어서 해석해야 최소비용인지 알수없기 때문에, 모든 경우를 다 봐준다.

 

문장 : abcd

문장의 idx = 3 까지 해석을 한다고 가정할때, 다음과 같은 substring을 만든다.

 

abc

bc

c

 

위 과정을 문장의 길이만큼 반복해가며 dp테이블을 채워나가면된다. dp테이블의 마지막값이 초기화 안되어있다면 -1 을 출력하면 답.

 

메인 계산 함수

    private int getDp(int idx){
        if(idx == word.length()){
            if(dp[word.length()-1] == 987654321) return -1;
            return dp[word.length()-1];
        }
        ArrayList<String> partitionWordList = partitionWord(word.substring(0, idx+1));
        for(int i = 0; i < partitionWordList.size(); i++){
            String shuffleWord = partitionWordList.get(i);
            int from = i; // mainWord의 분할의 시작된 idx를 나타냄
            for(int j = 0; j < dictionary.size(); j++){
                String originWord = dictionary.get(j);
                if(!compareAlphabet(shuffleWord, originWord)) continue;
                int diffWordCnt = compareWord(shuffleWord, originWord);
                if(from-1 < 0){ 
                    dp[idx] = Math.min(dp[idx], diffWordCnt);
                    continue;
                }
                dp[idx] = Math.min(diffWordCnt + dp[from-1], dp[idx]);
            }
            
        }
        return getDp(idx+1);
    }

---

전체 소스코드

https://github.com/devxb/JJUNalgo/tree/master/1099%20%EC%95%8C%20%EC%88%98%20%EC%97%86%EB%8A%94%20%EB%AC%B8%EC%9E%A5

devxb/JJUNalgo