시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 69 17 14 50.000%

문제

태수는 25년간의 오랜 노력 끝에 알파벳 A, B, C를 익혔다. 인생의 최대 성과를 낸 태수는 이를 기념하는 놀이를 만들었다. 그 놀이는 빈 문자열에서 시작해서 A, B, C로만 이루어진 문자열 S를 만드는 놀이이다. 태수는 1초 동안 아래의 작업 중 하나를 수행할 수 있다.

  • 문자열의 임의의 위치에 A를 추가한다.
  • 문자열의 임의의 위치에 B를 추가한다.
  • 문자열의 임의의 위치에 C를 추가한다.
  • 문자열의 임의의 위치에 ABC를 추가한다.

태수가 문자열 S를 만드는데 걸리는 최소 시간을 구해서 좀 더 빠르게 놀이를 마칠 수 있도록 도와주자!

입력

첫째 줄에 A, B, C로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 500)

출력

문자열 S를 만드는 데에 걸리는 최소 시간을 출력한다.

예제 입력 1

AABBCC

예제 출력 1

4

“” -> “A” -> “AABC” -> “AABBC” -> “AABBCC” 의 순으로 하면 4초에 주어진 문자열을 완성할 수 있다. 이외에도 여러가지 방법이 있지만 이보다 빠르게 하는 것은 불가능하다.

예제 입력 2

ABABCC

예제 출력 2

2

“” -> “ABC” -> “ABABCC” 의 순으로 하면 2초에 주어진 문자열을 완성할 수 있다.

출처