BOJ 25967 - 교수님 서운해 잉잉 링크
(2024.04.04 기준 P5)

문제

다음과 같은 자판이 주어진다. 문자와 문자 사이의 거리는 두 문자 자판의 중심 점 사이의 유클리드 거리의 제곱으로 정의한다.

두 문자열 사이의 유사도를 비교하는 방법은 아래와 같다.
1. 두 문자열에 공백을 적절히 추가해 길이를 같게 만든다. 이 때 공백은 문자열의 어디에도 추가될 수 있다.
2. 두 문자열을 앞부터 비교해 두 문자 중 하나 이상이 공백인 경우 $1\,600$점, 두 문자가 모두 알파벳이라면 두 문자 사이의 거리만큼의 점수를 더한다.
가능한 점수의 최솟값이 낮을수록 두 문자열의 유사도가 높은 것으로 판단한다.

$N$개의 단어 $W_1$, $\dots$, $W_N$과 단어 $T$가 주어질 때, $N$개의 단어 중 단어 $T$와 가장 유사도가 높은 단어를 출력

알고리즘

DP + 최적화

풀이

$W_k$와 $T$의 점수를 구한다고 가정하자. 이때 $dp(i, j)$를 $W_k$의 $i$번째, $T$의 $j$번째까지 고려했을 때의 최적값이라고 정의하자.

우리가 할 수 있는 행동은 총 $3$가지다.
1. $W_k$의 $i$번째 문자를 공백과 매칭한다. $dp(i - 1, j) + 1\,600$.
2. $T$의 $j$번째 문자를 공백과 매칭한다. $dp(i, j - 1) + 1\,600$.
3. $W_k$의 $i$번째 문자와 $T$의 $j$번째 문자를 매칭한다. $dp(i - 1, j - 1) + dist(W_{k_i}, T_j)$. 이때 $dist(a, b)$는 $a$와 $b$의 거리를 의미한다.
위 세 행동을 $O(N^2)$에 처리하면 된다.

공백은 $1\,600$점인데, 이는 어떤 문자 간 거리보다 더 높다. 그러므로 쓸모없는 공백 매칭을 하더라도 결국은 최적값을 찾아가게 된다.

문자 간 거리는 구하기 쉽다. 각 문자의 위치를 전처리해놓고 거리를 구하면 된다.
그런데 잘 생각해보자. 거리를 구하는 횟수는 최대 $500^3 = 125\,000\,000$이다. 시간 제한이 1.5초인데 제곱 연산을 $125\,000\,000$을 한다? TLE가 날 것이다.

문자는 알파벳 대문자로만 이루어져서 총 $26$개이며, 문자 간 거리의 개수는 $26^2$개이다. 전처리를 할 수 있으므로, 시간 복잡도의 상수를 최대한 줄이면 AC를 받을 수 있다.

코드

• C++

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> pii;

const int inf = 1e9;

// 문자 간 거리
int distance(pii a, pii b){
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // 문자 간 거리를 전처리하자.
    pii p[26] = {{3, 6}, {21, 10}, {13, 10}, {11, 6}, {10, 2}, {15, 6}, {19, 6}, {23, 6}, {30, 2}, {27, 6}, {31, 6}, {35, 6}, {29, 10}, {25, 10}, {34, 2}, {38, 2}, {2, 2}, {14, 2}, {7, 6}, {18, 2}, {26, 2}, {17, 10}, {6, 2}, {9, 10}, {22, 2}, {5, 10}};
    int dist[26][26];
    for (int i = 0; i < 26; i++) for (int j = i; j < 26; j++) dist[i][j] = dist[j][i] = distance(p[i], p[j]);

    int N; cin >> N;
    string W[N]; for (int i = 0; i < N; i++) cin >> W[i];
    string T; cin >> T;

    int res = inf;
    vector<string> ans;
    int dp[501][501];
    for (int k = 0, n, m = T.size(); k < N; k++){
        n = W[k].size();

        // dp(i, j): W[k]의 i번째, T의 j번째까지 고려했을 때의 최적값
        fill(&dp[0][0], &dp[n][m + 1], inf);
        dp[0][0] = 0;
        for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++){
            if (i) // W[k]의 i번째는 공백으로 매칭
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1600);
            if (j) // T의 j번째는 공백으로 매칭
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1600);
            if (i && j) // W[k]의 i번째와 T의 j번째를 매칭
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + dist[W[k][i - 1] - 65][T[j - 1] - 65]);
        }

        // 정답 갱신
        if (res > dp[n][m]){
            res = dp[n][m];
            ans.clear();
            ans.push_back(W[k]);
        }
        else if (res == dp[n][m]) ans.push_back(W[k]);
    }

    sort(ans.begin(), ans.end());
    for (string &word: ans) cout << word << '\n';
}

• Python (PyPy3)

import sys; input = sys.stdin.readline
from math import inf

# 문자 간 거리
def distance(a, b):
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

# 문자 간 거리를 전처리하자.
p = [(3, 6), (21, 10), (13, 10), (11, 6), (10, 2), (15, 6), (19, 6), (23, 6), (30, 2), (27, 6), (31, 6), (35, 6), (29, 10), (25, 10), (34, 2), (38, 2), (2, 2), (14, 2), (7, 6), (18, 2), (26, 2), (17, 10), (6, 2), (9, 10), (22, 2), (5, 10)]
dist = [[0] * 26 for _ in range(26)]
for i in range(26):
    for j in range(i, 26):
        dist[i][j] = dist[j][i] = distance(p[i], p[j])

N = int(input())
W = [input().strip() for _ in range(N)]
T = input().strip()

res = inf
ans = []
for k in range(N):
    n = len(W[k])
    m = len(T)

    # dp(i, j): W[k]의 i번째, T의 j번째까지 고려했을 때의 최적값
    dp = [[inf] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    for i in range(n + 1):
        for j in range(m + 1):
            if i: # W[k]의 i번째는 공백으로 매칭
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1600)
            if j: # T의 j번째는 공백으로 매칭
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1600)
            if i and j: # W[k]의 i번째와 T의 j번째를 매칭
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + dist[ord(W[k][i - 1]) - 65][ord(T[j - 1]) - 65])

    # 정답 갱신
    if res > dp[n][m]:
        res = dp[n][m]
        ans.clear()
        ans.append(W[k])
    elif res == dp[n][m]:
        ans.append(W[k])

ans.sort()
for word in ans:
    print(word)