영감
시간 제한1초메모리 제한256 MB
2부터 N까지의 진법 가운데 N을 나타냈을 때 자릿수 합이 가장 크게 되는 진법을 찾습니다. 최댓값이 같으면 가장 작은 진법을 고릅니다.
문제
원준이가 어렸을 때 이런 문제를 풀어 보았다.
‘?에 들어갈 수로 알맞은 것은?’
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 ≤ 105)
출력
첫째 줄에 자릿수 합의 최댓값과, 이때의 진법 수를 공백을 사이에 두고 출력한다.
만약 최댓값이 나오는 경우가 여러 가지이면 가장 작은 진법 수를 출력한다.