3D 프린터로 조각상 출력하기

면접 대비

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

요약

하루에 조각상 하나 또는 새 프린터 하나를 만드는 프린터 한 대가 있을 때, 조각상 n개 이상을 만드는 최소 일수를 구한다.

난이도: 보통10점 중 5점
유형: 그리디, 수학, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

3D 프린터가 한 대 있고, 이 프린터로 조각상 $n$ 개를 만들어야 한다. 조각상을 하나씩 출력하면 시간이 오래 걸리므로, 가지고 있는 프린터로 새 프린터를 먼저 출력하는 편이 빠를 수도 있다. 새로 만든 프린터도 조각상을 출력하거나 또 다른 프린터를 출력할 수 있다.

출력 작업은 하나에 꼬박 하루가 걸린다. 매일 가지고 있는 프린터마다 조각상을 출력할지 새 프린터를 출력할지 고를 수 있다. 어느 날 출력된 프린터는 다음 날부터 쓸 수 있고, 작업을 해도 프린터 자체는 없어지지 않는다.

조각상을 $n$ 개 이상 출력하는 데 필요한 최소 일수를 구하라.

입력

첫째 줄에 만들어야 하는 조각상의 개수 $n$ 이 주어진다. ( $1 \le n \le 10000$ )

출력

조각상을 $n$ 개 이상 출력하는 데 필요한 최소 일수를 한 줄에 출력한다.

예제2

예제 1
입력
```
1
```
예상 출력
```
1
```
예제 2
입력
```
5
```
예상 출력
```
4
```