[백준/2320] 끝말잇기 (Python)

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

2320번: 끝말잇기

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:13:31

 

---

 

문제 설명

 

 

백승환와 이석원은 한 팀이 되어 English 끝말대회에 출전했다. 앞단어의 마지막 글자가 뒷단어의 처음 글자와 같도록 단어를 차례대로 늘어놓는 게임 말이다. 단어는 주어지는 사전에 나와 있는 단어만 사용해야 하며 (영혼이 맑아질 만한 사실을 한 가지 가르쳐 주자면) 사전의 단어들은 모두 모음(A, E, I, O, U)으로만 이루어져있다는 것이다. 단어의 시작은 어떤 단어이든지 상관이 없고 같은 단어가 두 번 이상 사용되면 안 되며 게임에 사용된 단어의 길이의 합이 그 팀의 점수가 된다.

점수가 최대가 되도록 끝말잇기 규칙에 맞게 단어를 늘어놓는 프로그램을 만들어 승환이와 석원이를 도와주도록 하자.

 

 

입력 및 출력

 

입력

 

첫 줄에 사전에 포함된 단어 개수 N이 입력된다. (1 ≤ N ≤ 16)

두 번째 줄부터 N+1번째 줄까지 사전에 포함된 단어들이 한 줄에 하나씩 입력된다. 단어는 대문자 A, E, I, O, U로만 이루어져 있고 하나의 단어는 그 길이가 100을 넘지 않는다. 같은 단어가 두 번 주어지지 않는다.

 

출력

 

한 줄에 단어를 잘 늘어 놨을 때 얻을 수 있는 최대 점수를 출력한다.

 

입력 예시

 

3
AEIOU
UIU
EO

 

출력 예시

 

8

 

 

---

 

풀이

 

비트마스킹과 DP를 이용해 풀이해볼 수 있다.

 

시작 글자와 끝 글자는 최대 5가지, 최대 방문 경우의 수는 2 ^ 16이므로 25 * 2^16번의 dp로 이어볼 수 있겠다.

• DP[i][j][k] 를 총 i위치를 방문하고 시작 글자가 j, 끝 글자가 k인 경우의 길이값으로 두자.
• 그렇다면,
  • i위치에 방문하지 않고
  • 시작 글자가 k인 새로운 단어를 이어붙일 수 있다.
• 이 때 새로운 단어를 (start, ... , end)꼴로 두고, 길이가 length이며, 이 단어의 인덱스를 l이라고 두자. (start = k, i & (1 << l) = 0)
• 그렇다면 DP[i | (1 << l)][j][end] = DP[i][j][k] + length 가 성립한다.

 

 

풀이 코드

import sys
input = sys.stdin.readline

word_dict = ['A', 'E', 'I', 'O', 'U']
word_dict = { key : val for val, key in enumerate(word_dict)}

N = int(input())
word_list = [input().strip() for _ in range(N)]
dp = [[[0]*5 for _ in range(5)] for _ in range(1 << N)]
ans = 0

for i in range(N) :
  word = word_list[i]
  start, end = word_dict[word[0]], word_dict[word[-1]]
  dp[1 << i][start][end] = len(word)
  ans = max(ans, len(word))

for i in range(1, 1 << N) :
  for j in range(5) :
    for k in range(5) :
      if not dp[i][j][k] :
        continue
      for l in range(N) :
        if i & (1 << l) :
          continue
        word = word_list[l]
        start, end = word_dict[word[0]], word_dict[word[-1]]
        if k != start :
          continue
        dp[i | (1 << l)][j][end] = dp[i][j][k] + len(word)
        ans = max(ans, dp[i | (1 << l)][j][end])
print(ans)

풀이 완료!