수식 표현
시간 제한2초메모리 제한128 MB
덧셈, 곱셈, 팩토리얼, 괄호만으로 n을 표현할 때 필요한 최소 1의 개수를 구하는 문제입니다.
문제
수식 표현은 문자 1, 연산자 +, *, !, 괄호 (, )만으로 이루어진 식이다. 다음 규칙으로 정의한다.
1은 수식 표현이다.e가 수식 표현이면(e)와e!도 수식 표현이다.e1과e2가 수식 표현이면e1+e2와e1*e2도 수식 표현이다.
예를 들어 값 18을 나타내는 수식 표현으로는 (1+1+1)*(1+1+1)!, (1+1+1+1)*(1+1+1)+(1+1+1)! 등이 있다.
정수 n이 주어질 때, 값이 n인 수식 표현 중에서 사용하는 1의 개수가 최소인 경우의 개수를 구하라.
입력
첫째 줄에 정수 n이 주어진다.
- 1 ≤ n ≤ 10,000
출력
값이 n인 수식 표현을 만들기 위해 필요한 1의 최소 개수를 출력한다.
힌트
18 = (1+1+1)*(1+1+1)!