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

Problem : https://www.acmicpc.net/problem/1099

1099번: 알 수 없는 문장

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:14:53

 

---

 

문제 설명

 

 

형택이와 그의 친구들은 자꾸 다른 사람들이 대화를 엿듣는 것이 짜증났다. 따라서, 새로운 언어를 만들었다.

이 언어에는 단어가 N개 있다. 그리고 이 언어의 문장은 단어를 공백없이 붙여쓴 것이다. 이 문장에서 각 단어는 0번 또는 그 이상 나타날 수 있다. 이 언어가 형택스러운 이유는 (특별한 이유는) 단어에 쓰여 있는 문자의 순서를 바꿔도 되기 때문이다. 이때, 원래 단어의 위치와 다른 위치에 있는 문자의 개수 만큼이 그 순서를 바꾼 단어를 만드는 비용이다. 예를 들어, abc란 단어가 있을 때, abc는 비용 0으로 만들 수 있고, acb, cba, bac는 비용 2로 바꿀 수 있고, bca, cab는 비용 3으로 바꿀 수 있다.

따라서, 한 문장을 여러 가지 방법으로 해석할 수 있다. 이때 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 문장이 주어진다. 문장의 길이는 최대 50이다. 둘째 줄에 단어의 개수 N이 주어지며, N은 50보다 작거나 같은 자연수이다. 셋째 줄부터 N개의 줄에 각 단어가 주어진다. 단어의 길이는 최대 50이다. 문장과 단어는 알파벳 소문자로만 이루어져 있다.

 

출력

 

첫째 줄에 문제의 정답을 출력한다. 만약 문장을 해석할 수 없다면 -1을 출력한다.

 

입력 예시

 

neotowheret
4
one
two
three
there

 

출력 예시

 

8

 

 

---

 

풀이

 

DP 문제. 

 

• 같은 길이의 단어 둘의 비용을 체크하는 방법은 간단하다. 소스 단어를 기준으로 각 자리의 글자가 타겟 단어의 글자와 다르다면 1을 추가하면 된다.
  • 단, 구성 요소는 전부 동일해야 하므로, 소스와 타겟 단어를 카운팅하도록 하자.
• DP[i]를 i 미만의 index의 부분 문장들로 단어들을 조합하였을 때의 비용의 최솟값이라고 하자. 이후 DP[i+j] (1 <= j, i + j <= 전체 문장 길이)를 업데이트할 때, 타겟 단어는 i부터 i+j-1까지의 문자로 구성된 단어가 된다. 미리 저장된 단어사전의 각 단어들과 비용을 비교하여, 만일 유효한 비용이 나온다면 DP[i+j] = min(DP[i+j], DP[i] + cost)가 성립한다.

 

풀이 코드

from collections import defaultdict
import sys
input = sys.stdin.readline
MAX = float('inf')
sentence = input().strip()
N = int(input())
word_list = [list() for _ in range(51)]

for i in range(N) :
  word = input().strip()
  word_list[len(word)].append(word)

def word_distance(source, target) :
  dist = 0

  source_dict = defaultdict(int)
  target_dict = defaultdict(int)
  for i in range(len(source)) :
    source_dict[source[i]] += 1
    target_dict[target[i]] += 1
    if source[i] != target[i] :
      dist += 1

  for key in source_dict.keys() :
    if source_dict[key] != target_dict[key] :
      return -1

  return dist

dp = [MAX]*(len(sentence)+1)
dp[0] = 0

for i in range(len(sentence)) :
  if dp[i] == MAX : 
    continue
  target = sentence[i]
  for j in range(1, 51) :
    if i+j > len(sentence) :
      break
    for word in word_list[j] :
      dist = word_distance(word, target)
      if dist == -1 :
        continue
      dp[i+j] = min(dp[i+j], dp[i] + dist)
    if i+j < len(sentence) :
      target += sentence[i+j]

print(dp[-1] if dp[-1] < MAX else -1)

풀이 완료!