16715번 - Inspiration

원준이가 어렸을 때 이런 문제를 풀어 보았다.

‘?에 들어갈 수로 알맞은 것은?’

10, 11, 12, 13, 14, 15, 16, 17, 20, 22, 24, 31, 100, ?, 10000

이 문제를 보고 원준이는 자신있게 ‘100하고 10000 사이면 당연히 1000이지!’ 라는 생각으로 문제를 풀었고, 답이 121이라는 사실을 알고 충격에 빠졌다.

위에서 제시된 수열이 16을 16진법, 15진법, 14진법, ... 2진법으로 순서대로 나타낸 것임을 알게 된 원준이는 이에 영감을 얻어 ‘그럼, 자릿수의 합이 제일 클 때가 언제지?’ 라는 생각을 하고, 곧 16을 9진법으로 나타낸 결과 17의 자릿수의 합이 8로 가장 크다는 것을 알게 되었다.

이에 만족하지 못한 원준이는 1부터 100,000까지의 모든 자연수에 대하여 이 질문을 해결해보려고 한다.

입력으로 자연수 N이 주어졌을 때, 2진법부터 N진법까지 총 N-1개의 서로 다른 진법 체계 중, N의 자릿수의 합이 가장 크게 되는 경우를 구하여라.

주의: 40을 25진법으로 나타내면 40=1×25+15 이므로 자릿수의 합은 16이다.

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 10⁵)

첫째 줄에 자릿수 합의 최댓값과, 이때의 진법 수를 공백을 사이에 두고 출력한다.

만약 최댓값이 나오는 경우가 여러 가지이면 가장 작은 진법 수를 출력한다.