rlatjwls3333   7달 전

문제

얼마 전, 새로운 세대의 타자기가 발명되었다. 누구나 긴 글을 가능한 한 빨리 작성하고 싶어 한다. 바로 이런 목적을 위해 이 타자기가 제안되었다.

일반적인 타자기가 가진 키 집합(문자 키와 줄바꿈 키) 외에, 이 타자기에는 두 개의 새로운 키가 추가되었다.

첫 번째 키는, 마지막으로 입력한 문자가 커서와 같은 줄에 있을 때만 그 문자를 지운다.

두 번째 키는, 이전 줄의 마지막 단어를 현재 줄에 한 번에 입력한다. 다만 이 실험적인 모델의 특성상, 이 키는 현재 커서가 새로운 줄의 시작에 있고, 그 줄에 아직 아무 문자도 입력되지 않았을 때만 사용할 수 있다. 또한 이 키를 누르면, 복사된 단어를 현재 줄에 삽입한 뒤 커서는 그 단어의 끝으로 이동한다.

범인은 언제나 더 좋은 장비를 갖추고 있기 마련이고, 셜록 홈즈는 이를 잘 알고 있다. 그가 현재 수사 중인 사건에서 새로운 단서가 나타났다. 새로운 용의자가 체포되어 심문을 받았다. 전체 그림을 파악하기 위해 홈즈는, 이 사람이 사건과 관련된 암호문을 실제로 작성한 것인지, 아니면 다른 누군가가 작성한 것인지를 알아내고자 한다.

암호문은 n개의 단어로 이루어져 있으며, 각 단어는 서로 다른 한 줄씩 차지한다. 용의자는 감시를 받고 있었고, 이 암호문을 입력할 수 있었던 시간은 매우 짧았다는 것이 밝혀졌다. 홈즈는 그 시간 안에 이 사람이 정말로 이 암호문 전체를 입력할 수 있었는지 궁금해졌다.

이 텍스트를 조사하여, 이를 입력하는 데 필요한 최소 키 입력 횟수를 구하여라. 각 문자에 대해서는 그 문자를 바로 입력하는 키가 존재한다고 가정하라. 또한 줄바꿈 키, 현재 줄의 마지막 문자를 지우는 키, 이전 줄의 마지막 단어를 현재 줄에 복사하는 키도 사용할 수 있다. 단, 복사 키는 현재 줄에 아직 아무 문자도 입력되지 않았을 때만 사용할 수 있다.

입력

첫 번째 줄에 정수 n이 주어진다 — 암호문에 있는 단어의 개수이다.

다음 n개의 줄에는 암호문의 단어들이 주어진다. 단어는 대소문자 라틴 알파벳으로만 이루어져 있다. 모든 단어의 길이 합은 200000을 넘지 않으며, 모든 단어는 비어 있지 않다.

출력

암호문 전체를 입력하는 데 필요한 최소 키 입력 횟수를 나타내는 정수 하나를 출력하여라.

예제 입력 1

3
aaaa
aaab
CD

예제 출력 1

11

노트

예제에서는 다음 순서로 키를 누르면 된다.

aaaa{SP}{CP}{BS}b{SP}CD

여기서:

  • {SP}: 줄바꿈
  • {CP}: 이전 줄의 마지막 단어 복사
  • {BS}: 마지막 문자 삭제

댓글을 작성하려면 로그인해야 합니다.