독일 공공 카운팅 대회

면접 대비

시간 제한1초메모리 제한1024 MB

요약

n이 주어졌을 때, n부터 0까지 모든 수를 표시하는 데 필요한 숫자 표지판의 최소 개수를 구합니다.

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

문제

그레타는 세기를 좋아한다. 그녀는 일 년 내내 매일 연습한다. 계절에 따라 떨어지는 나뭇잎, 빗방울, 눈송이, 심지어 자라나는 잎까지 센다. 그러나 여름에 열리는 행사 하나가 그 무엇보다 으뜸이다. 바로 독일 공공 카운팅 대회(GCPC)다.

이 행사에서 그레타는 일주일 동안 전국의 카운팅 애호가들을 만나 세고, 또 세고, 계속 센다... 참가자들은 Glamorous Competitive Public Counting과 Great Chaotic Public Counting에도 함께 나간다. 주가 끝나면 모두 Golden Cup of Public Counting 우승을 노린다. 그녀가 가장 좋아하는 종목은 Gently Calming Public Counting이다. 군중이 침묵 속에서 세면서, 목표 숫자에 정확히 같은 순간 도달하도록 조화롭게 맞춘다.

그림 G.1: 카운트다운을 위해 팻말을 들고 있는 사람들.

긴장감을 높이고 Gently Calming Public Counting에 대비하려고, GCPC 조직위원회는 침묵 카운트다운으로 시작하기로 했다. 무대 위 사람들은 언제든 현재 숫자를 자릿수별 팻말을 들어 보여 준다. 팻말 하나에는 십진수 한 자리가 적혀 있다. $9$ 보다 큰 수는 팻말 여러 개를 나란히 들어 표시한다. 각 수는 가능한 가장 적은 개수의 팻말로 표시하며, 앞에 0을 채우지 않는다. 이렇게 무대 위 사람들은 $n, n-1, n-2, \dots$ 를 차례로 보여 주다가 마지막에 $0$ 을 보여 준다. GCPC가 곧 열리므로 조직위원회는 준비를 서둘러 끝내려 한다. $n$ 부터 $0$ 까지 카운트다운 전체를 보여 주려면 최소 몇 개의 팻말을 준비해야 하는가?

입력

입력은 다음과 같다.

카운트다운의 시작 수 $n$ ( $1 \le n \le 10^9$ )이 한 줄에 주어진다.

출력

카운트다운의 모든 수를 표시하는 데 필요한 팻말의 최소 개수를 출력한다.

힌트

첫 번째 예시에서 조직위원회는 숫자 $0$ 부터 $5$ 까지의 팻말을 각각 하나씩 준비해야 하므로 총 $6$ 개가 필요하다. 두 번째 예시에서는 $1$ 을 제외한 각 숫자의 팻말이 하나씩, $1$ 팻말이 두 개 필요하므로 총 $9+2=11$ 개가 필요하다.

예제5

예제 1
입력
```
5
```
예상 출력
```
6
```
예제 2
입력
```
20
```
예상 출력
```
11
```
예제 3
입력
```
44
```
예상 출력
```
14
```
예제 4
입력
```
271828182
```
예상 출력
```
82
```
예제 5
입력
```
314159265
```
예상 출력
```
82
```