시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 249 | 40 | 32 | 23.358% |
최소 편집 문제는 두 개의 문자열이 주어졌을 때 “삽입(insert)”, “삭제(delete)”, “대체(replace)”의 연산으로 하나의 문자열을 다른 하나의 문자열과 같게 만드는데 사용되는 최소 편집 회수를 구하는 문제이다. 하지만 이렇게 익히 알려진 문제를 또 다시 낼 리가 있겠는가? 그래서 문제에 새로운 편집기술이 하나가 추가되었는데 기존의 편집기술도 포함해서 다시 문제를 정리 해보도록 하자.
예를 들면 X = aabcc, Y = abcca와 같이 두 개의 문자열 X, Y가 주어진다. 이때 문자열 X에 다음의 편집기술을 최소로 사용해서 문자열 X가 문자열 Y와 같아지도록 만들어야 한다.
문자열 X, Y가 주어지면 위의 네 가지 편집기술을 사용하여 두 개의 문자열을 같게 만드는 최소 편집 회수를 구하시오.
첫 번째 줄에 문자열 X가 주어지고 두 번째 줄에 문자열 Y가 주어진다. 각 문자열의 길이는 1,000 이하이고, 알파벳 소문자로만 이루어져 있다.
최소 편집 회수를 출력한다.
abcdefg abdecgcabf
6