신작 게임의 지폐
시간 제한2초메모리 제한128 MB
1원부터 시작해 각 단위가 이전의 2~5배가 되는 K개의 지폐 단위를 정해, N원을 만드는 데 필요한 최소 지폐 수를 구하는 문제입니다.
문제
어떤 게임에서는 지폐를 화폐로 사용한다. 지폐의 액면가 구성은 다음 조건을 만족해야 한다.
- 서로 다른 액면가는 정확히 K가지이다.
- 가장 작은 액면가는 1원이다.
- i번째 액면가는 i-1번째 액면가의 2배, 3배, 4배, 5배 중 하나이다.
플레이어가 게임을 시작할 때 N원을 받는다. 같은 금액을 만들 수 있다면 지폐 수가 적을수록 좋다. 조건을 만족하는 액면가 구성을 자유롭게 정할 때, N원을 만들기 위해 필요한 지폐 수의 최솟값을 구하라.
입력
입력으로 두 정수 N과 K가 주어진다.
출력
N원을 만들기 위해 필요한 지폐 수의 최솟값을 출력한다.
제한
- 1 ≤ N ≤ 10^18
- 1 ≤ K ≤ 100