스파이 네트워크
시간 제한5초메모리 제한1024 MB
비밀 문구의 단어 10개 각각과 지정된 위치의 신문 단어 사이의 편집 거리를 구하여 출력합니다.
문제
NIS 스파이 네트워크는 추가 보안 조치로 본부 전화번호를 매일 바꾼다. 새 번호를 스파이에게 알리려고, 10개의 단어로 이루어진 비밀 문구를 스파이에게만 전달한다. 스파이는 문구의 단어를 신문 기사의 단어와 하나씩 비교한다. 각 쌍에서 첫 번째 단어를 두 번째 단어와 같게 만드는 데 필요한 연산의 최소 횟수를 구한다. 첫 번째 단어에 다음 연산을 수행할 수 있다.
- 연산 1 (INSERT): str1의 임의의 인덱스 앞이나 뒤에 임의의 문자를 삽입한다
- 연산 2 (REMOVE): str1에서 문자 하나를 삭제한다
- 연산 3 (REPLACE): str1의 임의의 인덱스에 있는 문자를 다른 문자로 바꾼다
입력
첫 줄에는 사용할 신문 단락의 단어 개수 N이 주어진다.
둘째 줄에는 10개의 위치가 주어진다. 각 위치는 단락에서 사용해야 할 단어를 가리킨다.
셋째 줄에는 비밀 문구의 단어 10개가 주어진다.
넷째 줄에는 단락의 단어 N개가 주어진다.
출력
구한 전화번호를 공백으로 구분하여 출력한다.
힌트
간단한 설명: 위 예시에서는 다음 단어 쌍의 편집 거리를 계산한다. hello와 amidst (6), I와 tranquil (8), cannot과 the (6), wait와 a (3), to와 cascade (7), start와 colors (5), coding과 dance (5), for와 the (3), this와 trees (3), problem과 in (7).