얼마 전, 새로운 세대의 타자기가 발명되었다. 누구나 긴 글을 가능한 한 빨리 작성하고 싶어 한다. 바로 이런 목적을 위해 이 타자기가 제안되었다.
일반적인 타자기가 가진 키 집합(문자 키와 줄바꿈 키) 외에, 이 타자기에는 두 개의 새로운 키가 추가되었다.
첫 번째 키는, 마지막으로 입력한 문자가 커서와 같은 줄에 있을 때만 그 문자를 지운다.
두 번째 키는, 이전 줄의 마지막 단어를 현재 줄에 한 번에 입력한다. 다만 이 실험적인 모델의 특성상, 이 키는 현재 커서가 새로운 줄의 시작에 있고, 그 줄에 아직 아무 문자도 입력되지 않았을 때만 사용할 수 있다. 또한 이 키를 누르면, 복사된 단어를 현재 줄에 삽입한 뒤 커서는 그 단어의 끝으로 이동한다.
범인은 언제나 더 좋은 장비를 갖추고 있기 마련이고, 셜록 홈즈는 이를 잘 알고 있다. 그가 현재 수사 중인 사건에서 새로운 단서가 나타났다. 새로운 용의자가 체포되어 심문을 받았다. 전체 그림을 파악하기 위해 홈즈는, 이 사람이 사건과 관련된 암호문을 실제로 작성한 것인지, 아니면 다른 누군가가 작성한 것인지를 알아내고자 한다.
암호문은 n개의 단어로 이루어져 있으며, 각 단어는 서로 다른 한 줄씩 차지한다. 용의자는 감시를 받고 있었고, 이 암호문을 입력할 수 있었던 시간은 매우 짧았다는 것이 밝혀졌다. 홈즈는 그 시간 안에 이 사람이 정말로 이 암호문 전체를 입력할 수 있었는지 궁금해졌다.
이 텍스트를 조사하여, 이를 입력하는 데 필요한 최소 키 입력 횟수를 구하여라. 각 문자에 대해서는 그 문자를 바로 입력하는 키가 존재한다고 가정하라. 또한 줄바꿈 키, 현재 줄의 마지막 문자를 지우는 키, 이전 줄의 마지막 단어를 현재 줄에 복사하는 키도 사용할 수 있다. 단, 복사 키는 현재 줄에 아직 아무 문자도 입력되지 않았을 때만 사용할 수 있다.
입력
첫 번째 줄에 정수 n이 주어진다 — 암호문에 있는 단어의 개수이다.
다음 n개의 줄에는 암호문의 단어들이 주어진다. 단어는 대소문자 라틴 알파벳으로만 이루어져 있다. 모든 단어의 길이 합은 200000을 넘지 않으며, 모든 단어는 비어 있지 않다.
rlatjwls3333 7달 전
문제
얼마 전, 새로운 세대의 타자기가 발명되었다. 누구나 긴 글을 가능한 한 빨리 작성하고 싶어 한다. 바로 이런 목적을 위해 이 타자기가 제안되었다.
일반적인 타자기가 가진 키 집합(문자 키와 줄바꿈 키) 외에, 이 타자기에는 두 개의 새로운 키가 추가되었다.
첫 번째 키는, 마지막으로 입력한 문자가 커서와 같은 줄에 있을 때만 그 문자를 지운다.
두 번째 키는, 이전 줄의 마지막 단어를 현재 줄에 한 번에 입력한다. 다만 이 실험적인 모델의 특성상, 이 키는 현재 커서가 새로운 줄의 시작에 있고, 그 줄에 아직 아무 문자도 입력되지 않았을 때만 사용할 수 있다. 또한 이 키를 누르면, 복사된 단어를 현재 줄에 삽입한 뒤 커서는 그 단어의 끝으로 이동한다.
범인은 언제나 더 좋은 장비를 갖추고 있기 마련이고, 셜록 홈즈는 이를 잘 알고 있다. 그가 현재 수사 중인 사건에서 새로운 단서가 나타났다. 새로운 용의자가 체포되어 심문을 받았다. 전체 그림을 파악하기 위해 홈즈는, 이 사람이 사건과 관련된 암호문을 실제로 작성한 것인지, 아니면 다른 누군가가 작성한 것인지를 알아내고자 한다.
암호문은
n개의 단어로 이루어져 있으며, 각 단어는 서로 다른 한 줄씩 차지한다. 용의자는 감시를 받고 있었고, 이 암호문을 입력할 수 있었던 시간은 매우 짧았다는 것이 밝혀졌다. 홈즈는 그 시간 안에 이 사람이 정말로 이 암호문 전체를 입력할 수 있었는지 궁금해졌다.이 텍스트를 조사하여, 이를 입력하는 데 필요한 최소 키 입력 횟수를 구하여라. 각 문자에 대해서는 그 문자를 바로 입력하는 키가 존재한다고 가정하라. 또한 줄바꿈 키, 현재 줄의 마지막 문자를 지우는 키, 이전 줄의 마지막 단어를 현재 줄에 복사하는 키도 사용할 수 있다. 단, 복사 키는 현재 줄에 아직 아무 문자도 입력되지 않았을 때만 사용할 수 있다.
입력
첫 번째 줄에 정수
n이 주어진다 — 암호문에 있는 단어의 개수이다.다음
n개의 줄에는 암호문의 단어들이 주어진다. 단어는 대소문자 라틴 알파벳으로만 이루어져 있다. 모든 단어의 길이 합은200000을 넘지 않으며, 모든 단어는 비어 있지 않다.출력
암호문 전체를 입력하는 데 필요한 최소 키 입력 횟수를 나타내는 정수 하나를 출력하여라.
예제 입력 1
예제 출력 1
노트
예제에서는 다음 순서로 키를 누르면 된다.
aaaa{SP}{CP}{BS}b{SP}CD여기서:
{SP}: 줄바꿈{CP}: 이전 줄의 마지막 단어 복사{BS}: 마지막 문자 삭제