Informatica Online Judge

  No. 1 [1981 / 07BD]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 49   Total Tried : 55


The Champion of this Problem (C++) : gs16109 - 0ms / 137byte
My Best Submission (C++) : N/A

[coudeup.kr]

Background

숫자 1을 가장 좋아하는 교원이는 1이 아닌 숫자 n을 자신의 능력을 동원해서 1로 바꾸기를 즐겨한다. 교원이는 다음의 세 가지 능력을 가지고 있다.

n이 2로 나누어떨어지면 2로 나눈다.

n이 5로 나누어떨어지면 5로 나눈다.

n에서 1을 뺀다.

숫자 n을 1로 만들기 위한 교원이의 능력 사용 최소 횟수를 알려주는 프로그램을 작성하시오.

예를 들어, n이 10일 때 10→5→4→2→1 로 4번 만에 1이 될 수도 있고, 10→2→1로 2번 만에 1이 될 수도 있다. 따라서 능력을 사용하는 최소 횟수는 22이다.

Input

첫 행에 1이 아닌 자연수 n이 주어진다.(단, 1 < n <= 100,000)

Output

교원이의 능력 사용 최소 횟수를 출력한다.

IO Example

입력
10

출력
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]