시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 147 36 26 34.211%

문제

세준이는 동그랗게 생긴 사탕 통을 가지고 있다. 그 사탕 통에는 N개의 칸이 원형으로 동그랗게 자리잡고 있으며, 1번부터 N번까지 시계방향으로 번호가 매겨져 있다.

처음에 세준이는 사탕을 아무 칸에나 넣을 수 있다. 그 다음부터는 사탕이 들어 있는 칸 번호의 각 자리 숫자의 합을 구하여, 그 값만큼 시계방향으로 이동한다. 예를 들어 123번 칸에 사탕이 있으면 6칸만큼 시계방향으로 이동한다. 사탕을 계속 이동시키다가 이전에 방문한 칸이 나오면 멈춘다. 처음에 사탕을 넣은 칸도 방문한 칸으로 취급한다.

사탕 통의 크기가 주어지면, 사탕을 적절한 칸에 넣었을 때 최대 몇 개의 칸을 방문할 수 있는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 200,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 방문할 수 있는 최대 칸의 개수를 출력한다.

예제 입력 1

4

예제 출력 1

3

예제 입력 2

5

예제 출력 2

4

예제 입력 3

17

예제 출력 3

11

예제 입력 4

566

예제 출력 4

176

출처

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: jh05013