이모티콘

면접 대비

시간 제한2초메모리 제한512 MB

요약

화면에 이모티콘 1개가 있고 클립보드는 비어 있을 때, 복사, 붙여넣기, 하나 삭제 연산만으로 정확히 S개를 만드는 최소 시간을 구한다.

난이도: 보통10점 중 5점
유형: BFS, 그래프, 동적 계획법, 구현
정답자: 아직 제출이 없습니다

문제

영선이는 기분이 좋아서 효빈이에게 스마일 이모티콘을 $S$ 개 보내려고 한다.

화면에는 이미 이모티콘이 1개 입력되어 있다. 영선이는 다음 세 가지 연산만 써서 화면의 이모티콘을 $S$ 개로 만들려고 한다.

화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
클립보드에 있는 이모티콘을 모두 화면에 붙여넣는다.
화면에 있는 이모티콘 중 하나를 삭제한다.

연산 하나에 1초가 걸린다. 복사하면 클립보드에 있던 이전 내용은 지워진다. 클립보드가 비어 있으면 붙여넣을 수 없고, 화면에 있는 이모티콘 중 일부만 복사할 수도 없다. 클립보드에 있는 이모티콘 중 일부만 삭제할 수도 없다. 붙여넣으면 클립보드에 있는 이모티콘 개수만큼 화면의 개수가 늘어난다.

영선이가 화면에 이모티콘을 $S$ 개 만드는 데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $S$ 가 주어진다. ( $2 \le S \le 1000$ )

출력

첫째 줄에 이모티콘을 $S$ 개 만드는 데 필요한 시간의 최솟값을 출력한다.

예제4

예제 1
입력
```
2
```
예상 출력
```
2
```
예제 2
입력
```
4
```
예상 출력
```
4
```
예제 3
입력
```
6
```
예상 출력
```
5
```
예제 4
입력
```
18
```
예상 출력
```
8
```