시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 256 MB 70 18 16 41.026%

문제

브루는 지금 매우 비효율적인 편집기로 글을 쓰고 있다. 브루는 편집기로 원하는 글을 쓰려고 한다.

편집기에는 임시 저장 공간인 스택이 마련되어 있어서, 이 스택을 이용해 글을 쓸 수 있다. 편집기가 지원하는 연산은 다음 세 가지뿐이다.

  1. 스택 뒤에 하나의 문자를 추가한다.
  2. 스택 맨 뒤의 문자를 하나 제거한다. 스택이 비어 있을 때는, 아무 것도 하지 않는다.
  3. 스택에 저장된 문자열을 글에 붙여 넣는다. 이때 스택은 그대로 유지된다.

브루를 위해, 원하는 글을 쓰기 위한 연산의 최소 횟수를 계산해 보자. 글을 모두 쓴 뒤, 스택의 상태는 비어 있지 않아도 된다.

입력

브루가 편집기를 이용해 쓰고 싶은 글 S가 주어진다. (1 ≤ |S| ≤ 2000)

S는 알파벳 소문자로만 이루어져 있다.

출력

브루가 글을 쓰기 위해 해야 하는 연산의 최소 횟수를 출력한다.

예제 입력 1

ababc

예제 출력 1

5

다음과 같은 방법으로 5회의 연산만에 ababc를 출력할 수 있다.

  1. a를 스택에 추가한다. (스택: a, 글: 비어 있음)
  2. b를 스택에 추가한다. (스택: ab, 글: 비어 있음)
  3. 스택에 있는 문자열을 글에 붙여 넣는다. (스택: ab, 글: ab)
  4. c를 스택에 추가한다. (스택: abc, 글: ab)
  5. 스택에 있는 문자열을 글에 붙여 넣는다. (스택: abc, 글: ababc)

예제 입력 2

whyamihere

예제 출력 2

11

스택에 전체 문자열을 추가한 뒤, 한 번 출력하는 것이 최적이다.

출처

High School > 서울과학고등학교 > 2020 SciOI #1 B번