2320 - 끝말잇기
본문
백승환와 이석원은 한 팀이 되어 English 끝말대회에 출전했다. 앞단어의 마지막 글자가 뒷단어의 처음 글자와 같도록 단어를 차례대로 늘어놓는 게임 말이다. 단어는 주어지는 사전에 나와 있는 단어만 사용해야 하며 (영혼이 맑아질 만한 사실을 한 가지 가르쳐 주자면) 사전의 단어들은 모두 모음(A, E, I, O, U)으로만 이루어져있다는 것이다. 단어의 시작은 어떤 단어이든지 상관이 없고 같은 단어가 두 번 이상 사용되면 안 되며 게임에 사용된 단어의 길이의 합이 그 팀의 점수가 된다.
점수가 최대가 되도록 끝말잇기 규칙에 맞게 단어를 늘어놓는 프로그램을 만들어 승환이와 석원이를 도와주도록 하자.
입력
첫 줄에 사전에 포함된 단어 개수 $N$이 입력된다. ($1 \leq N \leq 16$)
두 번째 줄부터 $N+1$번째 줄까지 사전에 포함된 단어들이 한 줄에 하나씩 입력된다. 단어는 대문자 A, E, I, O, U로만 이루어져 있고 하나의 단어는 그 길이가 $100$을 넘지 않는다. 같은 단어가 두 번 주어지지 않는다.
출력
한 줄에 단어를 잘 늘어 놨을 때 얻을 수 있는 최대 점수를 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 128MB |
풀이
단어를 여러개 붙여 하나의 긴 단어를 만들고, 그 단어의 길이가 점수가 된다고 한다. 그러면 최대의 점수를 얻기 위해서는 단어를 최대한 많이 붙이는 것이 좋을 것이다. 단어를 붙여나갈 수 있는 경우를 모두 계산하면 된다.
다만 그렇게 쉽지는 않다. 단어의 개수가 16개밖에 없지만, 가능한 모든 경우의 수인 $16!$은 $2 \times 10^{13}$이 넘는다. 당연히 모든 경우의 수를 탐색하는 것은 불가능. 탐색 횟수를 줄여야한다.
모든 경우를 탐색한다면 순서만 다르고 똑같은 단어를 사용했다는 그 상황을 여러번 탐색하게 될 것이다. 생각해보면 같은 단어를 사용했다면 점수는 그 단어의 길이이므로 모두 같을 것이다. 그러면 그 상황에서의 점수를 미리 기록해놓을 수 있다면 나중에 다시 탐색하지 않아도 그 결과를 가져올 수 있을 것이다. subproblem의 결과값을 기록하여 사용하는 방법이므로 DP 방식을 채용한다.
DP 문제로 해결하기 위해서는 2가지를 고려해야한다.
- 점화식을 만들 수 있는가?
- subproblem으로 어떻게 쪼개고, 어떠한 dp배열에 기록할 것인가?
점화식은 생각보다 간단하다. 현재 사용한 단어들과 그때의 점수를 알고 있다면, 지금까지 사용하지 않았던 단어들 중 끝말을 이을 수 있는 단어일 때, 점수는 현재까지의 점수 + 이번에 사용할 단어의 길이가 될 것이다. 만약 끝말을 이을 수 없다면 탐색하지 않아도 된다.
그러면 이것을 DP배열에 어떻게 기록할 수 있을까? 일단 끝말잇기는 마지막 글자만 기록하고 있으면 되므로 가능한 글자 (모음 5개) 만 기록하고 있으면 된다. 그러면 우리는 현재까지 사용한 단어만 기록할 수 있으면 된다.
여기서는 bitfield를 이용하여 구현하는 스킬이 일반적이다. 단어의 개수가 많지 않기 때문에 사용할 수 있는 방법이다. 각 단어에 순서를 매기고, 그 단어의 사용 여부를 $0$ 또는 $1$로 bit를 켜듯이 저장하는 것이다. 단어의 개수가 16개이므로 하나의 예시는 $0010\,0000\,0000\,0001$이 될 수 있다. 앞의 예시라면 1번째 단어와 14번째 단어를 사용했다는 뜻으로 받아들일 수 있다. (가장 오른쪽 bit가 1번 단어). 이렇게 bitfield를 이용하면 16개의 단어의 사용여부를 $2^{16} = 65536$개의 숫자로 전부 표현할 수 있다. 그러면 dp배열은 dp[5][65536]의 크기라면 모든 상황을 저장해둘 수 있게 된다.
다음으로는 비트필드를 적용하는 다이나믹 프로그래밍을 구현하면 된다. code 부분에서 search 함수가 그 역할을 수행한다. 순서를 따져보면 아래와 같다.
- 이미 탐색한 subproblem인 경우, dp값이 이미 배열에 저장되어있다. 그 값을 반환만 해주면 된다
- 중복 탐색 횟수를 매우 크게 줄일 수 있는 방법
- 탐색하지 않은 경우, 그 state의 점수는 파라미터로 주어졌다 ($s$)
- 모든 단어들에 대해, 현재 state에서 끝말을 이을 수 있는지 검사한다
- 끝말을 이을 수 있는 조건은, 현재 단어의 시작글자가 현재까지의 단어의 끝 글자와 같은지의 여부이다
- 끝말을 이을 수 있다면, visit 체크하고 현재 단어를 추가했을 때의 점수를 함께 다음 subproblem으로 넘긴다
이 때 최종적인 답은 가능한 모든 state에서 나오는 score들 중 최댓값이므로, dp배열에 특정 score를 저장할 때마다 최댓값으로 갱신해주도록 하자. 마지막에는 그 최종 결과만 출력하면 된다.
- 참고 알고리즘 : 다이나믹 프로그래밍
코드
사용 언어 : C
최종 수정일 : 2023 / 6 / 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdio.h>
typedef struct Node {
char start;
char end;
int score;
} ND;
#define MAX_IDX 16
ND arr[MAX_IDX];
int n;
int result = 0;
#define MAX_VOWEL 5
#define MAX_ALPHABET 26
int len(char* s) {
int t;
for (t = 0; s[t] != '\0'; ++t) {
}
return t;
}
int getVowelIndex(char x) {
switch (x) {
case 'A': {
return 0;
}
case 'E': {
return 1;
}
case 'I': {
return 2;
}
case 'O': {
return 3;
}
case 'U': {
return 4;
}
}
}
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define NOTVISIT -1
int dp[MAX_VOWEL][1 << MAX_IDX];
#define MAX_LEN 100
void read_input() {
scanf("%d", &n);
char str[MAX_LEN + 1];
for (int i = 0; i < n; ++i) {
scanf("%s", str);
int j = len(str);
arr[i] = (ND){str[0], str[j - 1], j};
}
return;
}
int search(char e, int v,int s) {
if (dp[getVowelIndex(e)][v] != NOTVISIT) {
return dp[getVowelIndex(e)][v];
}
dp[getVowelIndex(e)][v] = s;
result = max(result, s);
for (int i = 0; i < n; ++i) {
if ((arr[i].start == e) && ((v & (1 << i)) == 0)) {
search(arr[i].end, (v | (1 << i)), s + arr[i].score);
}
}
return dp[getVowelIndex(e)][v];
}
char vowel[MAX_VOWEL] = {'A', 'E', 'I', 'O', 'U'};
void solve() {
for (int i = 0; i < MAX_VOWEL; ++i) {
search(vowel[i], 0, 0);
}
return;
}
int main() {
read_input();
for (int i = 0; i < MAX_VOWEL; ++i) {
for (int j = 0; j < (1 << n); ++j) {
dp[i][j] = NOTVISIT;
}
}
solve();
printf("%d", result);
return 0;
}
- getVowelIndex(x) : 주어진 모음 ‘x’의 번호를 반환하는 함수
- 문자로 주어지는 것이 5개밖에 존재하지 않기 때문에, $0$ ~ $4$까지의 번호를 순서대로 적용