백준 #1230 문자열 거리

문자열 거리 문제는 "최장 공통 부분 문자열" 문제와 유사합니다.  동일하게 동적 프로그래밍 기법을 이용해야 하지만, 구현하려고 한다면, 조금 생각을 해야 합니다.  난이도는 Gold II 입니다.  정답률 32.7%의 문제네요.  정답자 40명정도로 난이도 책정된 것에 비해서는 상당히 적습니다.

 

Dynamic Programming

 

문제의 내용을 두개의 문자열이 주어졌을 때, 첫번째 문자열에 원하는만큼 문자열을 삽입해서 두번째 문자열을 만들고자 할 때, 문자열 삽입을 최소로 하고자 하는 문제입니다.  예를 들어서 "abcd" 란 문자열과 "abNORMAL cOMEdY"란 문자열이 주어졌다면, ab 와  c 사이에 "NORMAL "이란 문자열과 c와 d 사이에 "OME"라는 문자열, 그리고 d 뒤에 "Y"란 물자열을 삽입해야 하기 때문에 최소의 문자열 삽입은 3번이 됩니다.

 

이 문제를 작은 문제로 풀어보기 위해서 우리는 첫번째 문자열을 a, 두번째 문자열을 b라고 하고, \(d_{ij}\) 를 a 문자열의 앞부분 i까지의 문자열과 b문자열 앞부분 j까지의 문자열까지를 푸는 것으로 합니다.  즉, 문자열 거리값을 나타내도록 하는 것이죠.  0 이상의 값은 문자열 거리값이고, -1은 실패를 뜻합니다.  예를 들어서 "abc" 문자열과 "aababc" 문자열을 이용한다면, \(d_{ij}\) 는 다음과 같이 표로 나타낼 수 있습니다.

 

\(d_{ij}\)	{}	a	a	b	a	b	c
{}	0	1	1	1	1	1	1
a	-1	0	1	1	1	1	1
b	-1	-1	-1	1	2	1	2
c	-1	-1	-1	-1	-1	-1	1

 

이제 명확하게 \(d_{ij}\)를 정의했습니다.  하지만, 표를 만들어서 보면 조금 난해합니다.  이전값에서 어떻게 현재값을 뽑아낼 것인지가 궁금합니다.  그래서 궁리를 한 방법이, 현재 위치의 a[i], b[j] 가 서로 같아도, 같았을 때와 같지 않았을 때, 값을 따로 나눕니다.  즉, 이제 \(d_{ij}\) 값이 \(de_{ij}, dn_{ij}\)로 각각, 같은 경우와 같지 않은 경우로 나누어서 계산을 합니다.

 

\(de_{ij}\) / \(dn_{ij}\)	{}	a	a	b	a	b	c
{}	0 / -1	-1 / 1	-1 / 1	-1 / 1	-1 / 1	-1 / 1	-1 / 1
a	-1 / -1	0 / -1	1 / 1	-1 / 1	-1 / 1	-1 / 1	-1 / 1
b	-1 / -1	-1 / -1	-1 / -1	1 / -1	-1 / 2	1 / 2	-1 / 2
c	-1 / -1	-1 / -1	-1 / -1	-1 / -1	-1 / -1	-1 / -1	1 / -1

 

결과값은 \(d_{ij} = min( de_{ij}, dn_{ij} )\) 이 됩니다.  이 식을 계산하려면, 다음과 같은 식이 사용됩니다.  최소값을 계산해야 하므로, -1 은 INF 값으로 가정합니다.

 

\[ de_{ij} = \begin{cases} min(de_{i-1, j-1}, dn_{i-1,j-1}) & a_i = b_j \\ -1 & a_i \neq b_j \end{cases} \]

\[ dn_{ij} = min(de_{i, j-1}+1, dn_{i,j-1}) \]

 

이렇게 하면, 최종적으로 \( d_{ij} \) 값을 이용하면 됩니다.  이 값이 -1 이라면, a 문자열에 문자를 삽입해서 b 문자열을 만들 수가 없는 경우입니다.

 

다음은 제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

 

//------------------------------------------------------------------------------
//  baekjoon #1230 - String Distance
//    - by Aubrey Choi
//    - created at 2020-01-09
//------------------------------------------------------------------------------
#include <stdio.h>
#include <string.h>
#define  INF  1000

short dp[1001][1001][2];
short min(short a,short b) { return a<b?a:b; }
int main()
{
  int i, j, r, na, nb;
  char a[1004], b[1004];
  gets(a); gets(b);
  na=strlen(a); nb=strlen(b);
  if(na>nb) { puts("-1"); return 0; }
  for(i=1,dp[0][0][0]=0,dp[0][0][1]=INF;i<=nb;i++) dp[0][i][0]=INF,dp[0][i][1]=1;
  for(i=0;i<na;i++)
  {
    for(j=0;j<=i;j++) dp[i+1][j][0]=dp[i+1][j][1]=INF;
    for(j=i;j<nb;j++)
    {
      if(a[i]==b[j]) dp[i+1][j+1][0]=min(dp[i][j][0],dp[i][j][1]);
      else dp[i+1][j+1][0]=INF;
      dp[i+1][j+1][1]=min(dp[i+1][j][0]+1,dp[i+1][j][1]);
    }
  }
  r=min(dp[na][nb][0],dp[na][nb][1]);
  printf("%d\n",(r>=INF)?-1:r);
}