시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 24 15 11 91.667%

문제

종수는 아두이노 프로젝트에 사용할 도트 매트릭스 프린터를 하나 구매했다. 오랜 시간동안 아두이노와 프린터 사이의 통신을 연구하고 구현한 결과 프린터에 세 가지 명령을 내릴 수 있게 되었다.

  • SET(X): 프린터의 주 메모리에 글자 X를 저장한다.
  • NEXT(X): 프린터의 보조 메모리에 글자 X를 저장한다.
  • WRITE: 주 메모리에 저장되있는 글자를 인쇄한다. 바로 이전에 사용한 명령이 NEXT인 경우에는 보조 메모리에 저장된 글자를 출력한다.

예를 들어, "AABAA"를 출력하려면 아래와 같은 명령 8개를 입력하면 된다.

SET(A), WRITE, WRITE, SET(B), WRITE, SET(A), WRITE, WRITE. 

NEXT를 사용하면 7개로 인쇄할 수 있다.

SET(A), WRITE, WRITE, NEXT(B), WRITE, WRITE, WRITE. 

알파벳 대문자로만 이루어진 단어가 주어졌을 때, 이 단어를 출력하는데 필요한 명령 개수의 최소값을 구하는 프로그램을 작성하시오.

첫 번째 명령은 반드시 SET이어야 한다.

입력

첫째 줄에 인쇄해야하는 단어가 주어진다. 단어는 알파벳 대문자로만 이루어져 있으며, 길이는 10,000을 넘지 않는다. 

출력

입력으로 주어진 단어를 출력하는데 필요한 명령 개수의 최소값을 출력한다.

예제 입력 1

BABCBACA

예제 출력 1

13

힌트

SET(B), WRITE, NEXT(A), WRITE, WRITE, NEXT(C), WRITE, WRITE, SET(A), WRITE, NEXT(C), WRITE, WRITE. 

W3sicHJvYmxlbV9pZCI6IjMwOTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzYzRcdWQyYjggXHViOWU0XHVkMmI4XHViOWFkXHVjMmE0IFx1ZDUwNFx1YjliMFx1ZDEzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjODg1XHVjMjE4XHViMjk0IFx1YzU0NFx1YjQ1MFx1Yzc3NFx1YjE3OCBcdWQ1MDRcdWI4NWNcdWM4MWRcdWQyYjhcdWM1ZDAgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YjNjNFx1ZDJiOCBcdWI5ZTRcdWQyYjhcdWI5YWRcdWMyYTQgXHVkNTA0XHViOWIwXHVkMTMwXHViOTdjIFx1ZDU1OFx1YjA5OCBcdWFkNmNcdWI5ZTRcdWQ1ODhcdWIyZTQuIFx1YzYyNFx1Yjc5YyBcdWMyZGNcdWFjMDRcdWIzZDlcdWM1NDggXHVjNTQ0XHViNDUwXHVjNzc0XHViMTc4XHVjNjQwIFx1ZDUwNFx1YjliMFx1ZDEzMCBcdWMwYWNcdWM3NzRcdWM3NTggXHVkMWI1XHVjMmUwXHVjNzQ0IFx1YzVmMFx1YWQ2Y1x1ZDU1OFx1YWNlMCBcdWFkNmNcdWQ2MDRcdWQ1NWMgXHVhY2IwXHVhY2ZjIFx1ZDUwNFx1YjliMFx1ZDEzMFx1YzVkMCBcdWMxMzggXHVhYzAwXHVjOWMwIFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWIwYjRcdWI5YjQgXHVjMjE4IFx1Yzc4OFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+U0VUKFgpOiBcdWQ1MDRcdWI5YjBcdWQxMzBcdWM3NTggXHVjOGZjIFx1YmE1NFx1YmFhOFx1YjlhY1x1YzVkMCBcdWFlMDBcdWM3OTAgWFx1Yjk3YyBcdWM4MDBcdWM3YTVcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPk5FWFQoWCk6IFx1ZDUwNFx1YjliMFx1ZDEzMFx1Yzc1OCBcdWJjZjRcdWM4NzAgXHViYTU0XHViYWE4XHViOWFjXHVjNWQwIFx1YWUwMFx1Yzc5MCBYXHViOTdjIFx1YzgwMFx1YzdhNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+V1JJVEU6IFx1YzhmYyBcdWJhNTRcdWJhYThcdWI5YWNcdWM1ZDAgXHVjODAwXHVjN2E1XHViNDE4XHVjNzg4XHViMjk0IFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWM3NzhcdWMxYzRcdWQ1NWNcdWIyZTQuIFx1YmMxNFx1Yjg1YyBcdWM3NzRcdWM4MDRcdWM1ZDAgXHVjMGFjXHVjNmE5XHVkNTVjIFx1YmE4NVx1YjgzOVx1Yzc3NCBORVhUXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWJjZjRcdWM4NzAgXHViYTU0XHViYWE4XHViOWFjXHVjNWQwIFx1YzgwMFx1YzdhNVx1YjQxYyBcdWFlMDBcdWM3OTBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICZxdW90O0FBQkFBJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjgyNFx1YmE3NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YmE4NVx1YjgzOSA4XHVhYzFjXHViOTdjIFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlNFVChBKSwgV1JJVEUsIFdSSVRFLCBTRVQoQiksIFdSSVRFLCBTRVQoQSksIFdSSVRFLCBXUklURS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TkVYVFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWJhNzQgN1x1YWMxY1x1Yjg1YyBcdWM3NzhcdWMxYzRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+U0VUKEEpLCBXUklURSwgV1JJVEUsIE5FWFQoQiksIFdSSVRFLCBXUklURSwgV1JJVEUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YjJlOFx1YzViNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHViMmU4XHVjNWI0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViYTg1XHViODM5IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHViYTg1XHViODM5XHVjNzQwIFx1YmMxOFx1YjRkY1x1YzJkYyBTRVRcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3NzhcdWMxYzRcdWQ1NzRcdWM1N2NcdWQ1NThcdWIyOTQgXHViMmU4XHVjNWI0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU4XHVjNWI0XHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZTM4XHVjNzc0XHViMjk0IDEwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViMmU4XHVjNWI0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViYTg1XHViODM5IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5TRVQoQiksIFdSSVRFLCBORVhUKEEpLCBXUklURSwgV1JJVEUsIE5FWFQoQyksIFdSSVRFLCBXUklURSwgU0VUKEEpLCBXUklURSwgTkVYVChDKSwgV1JJVEUsIFdSSVRFLiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzA5OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IklTUElTIiwiZGVzY3JpcHRpb24iOiI8cD5QZXJpY2EgZ290IGFuIGFudGlxdWUgZG90IG1hdHJpeCBwcmludGVyIHRoYXQgaGUgY2FuIGJlIGNvbnRyb2wgdXNpbmcgaGlzIHBlcnNvbmFsIGNvbXB1dGVyLiBXaGlsZSBwbGF5aW5nIHdpdGggaGlzIG5ldyBvbGQgcHJpbnRlciBoZSBkaXNjb3ZlcmVkIHRoYXQgcHJpbnRlciByZWNvZ25pemVzIHRocmVlIHR5cGVzIG9mIGNvbW1hbmRzOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlNFVChYKSAmbmRhc2g7IFRoaXMgY29tbWFuZCBzZXRzIGNoYXJhY3RlciBYIGludG8gbWFpbiBtZW1vcnkuJm5ic3A7PFwvbGk+XHJcblx0PGxpPk5FWFQoWCkgJm5kYXNoOyBUaGlzIGNvbW1hbmQgc2V0cyBjaGFyYWN0ZXIgWCBpbnRvIHNlY29uZGFyeSBtZW1vcnkuJm5ic3A7PFwvbGk+XHJcblx0PGxpPldSSVRFICZuZGFzaDsgVGhpcyBjb21tYW5kIHdyaXRlcyBhIGNoYXJhY3RlciBvbiB0aGUgcGFwZXIuIFRoZSBjaGFyYWN0ZXIgdG8gYmkgcHJpbnRlZCBpcyByZWFkIGZyb20gdGhlIG1haW4gbWVtb3J5IHVubGVzcyBwcmV2aW91cyBjb21tYW5kIHdhcyBORVhULiBJbiB0aGF0IGNhc2UsIGNoYXJhY3RlciBpcyByZWFkIGZyb20gdGhlIHNlY29uZGFyeSBtZW1vcnkuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIG5leHQgOCBjb21tYW5kcyB3aWxsIHdyaXRlICZsZHF1bztBQUJBQSZyZHF1bzsgb24gdGhlIHBhcGVyOiZuYnNwOzxcL3A+XHJcblxyXG48cD5TRVQoQSksIFdSSVRFLCBXUklURSwgU0VUKEIpLCBXUklURSwgU0VUKEEpLCBXUklURSwgV1JJVEUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFmdGVyIGEgbG90IG9mIHRoaW5raW5nLCBQZXJpY2EgZGlzY292ZXJlZCB0aGF0IGhlIGNvdWxkIGFsc28gZG8gaXQgaW4gNyBjb21tYW5kczombmJzcDs8XC9wPlxyXG5cclxuPHA+U0VUKEEpLCBXUklURSwgV1JJVEUsIE5FWFQoQiksIFdSSVRFLCBXUklURSwgV1JJVEUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgc2VxdWVuY2Ugb2YgY2hhcmFjdGVycywgd3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBjYWxjdWxhdGUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGNvbW1hbmRzIG5lZWRlZCB0byBwcmludCB0aGF0IHNlcXVlbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD48c3Ryb25nPk5vdGU8XC9zdHJvbmc+OiBGaXJzdCBjb21tYW5kIGhhcyB0byBiZSBTRVQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgc2VxdWVuY2Ugb2YgY2hhcmFjdGVycyB0byBiZSBwcmludGVkLiBUaGUgc2VxdWVuY2UgY29udGFpbnMgdXBwZXIgY2FzZSBlbmdsaXNoIGxldHRlcnMgYW5kIGlzIG5vdCBsb25nZXIgdGhhbiAxMCAwMDAuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IG9uZSBpbnRlZ2VyLCB0aGUgbWluaW11bSBudW1iZXIgb2YgY29tbWFuZHMgbmVlZGVkIHRvIHByaW50IHRoZSBzZXF1ZW5jZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlNFVChCKSwgV1JJVEUsIE5FWFQoQSksIFdSSVRFLCBXUklURSwgTkVYVChDKSwgV1JJVEUsIFdSSVRFLCBTRVQoQSksIFdSSVRFLCBORVhUKEMpLCBXUklURSwgV1JJVEUuJm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=