image.png

문제 풀이

가격을 구성하는 숫자들을 재배열 하는데, 이전 가격 e이하이면서 m으로 나누어 떨어지는 숫자를 찾는 문제이다. 가격의 최대 자릿수가 14자리까지 가능하므로 단순한 완전 탐색으로는 풀 수 없는 문제이다.

가격이 될 수 있는 몇조개의 숫자를 모두 메모이제이션하면 부분 문제의 수가 너무 많아져 비효율적이 된다. 따라서 문제를 단순화 시켜 효율적인 메모이제이션을 구현해야 한다. 먼저 가격이 될 수 있는 숫자를 기록하는 이유를 생각해보자

  1. n자리를 모두 만들었는지 판단할 때
  2. 다 만든 가격이 m의 배수인지 확인할 때
  3. 다 만든 가격이 원래 가격보다 작은지 확인할 때

이 조건을 만족시키면서 최대한 부분 문제의 숫자를 줄여야 한다. 그에 앞서 사용 가능한 숫자들로 새로운 숫자를 만들 때 중복이 발생하는 문제를 해결해야 한다. 중복을 해결하는 방법은 새로운 숫자를 선택할 때 해당 숫자가 앞에 사용된 숫자와 같으면 사용하지 않는 것이다. 이 때 앞의 숫자와 이어져서 새로운 숫자가 만들어 지는 경우는 사용할 수 있다.

n자리를 모두 만들었는지 판단하는 건 새로운 숫자를 만드는 과정에서 해당 숫자들을 모두 사용했는지를 확인하면 되므로 간단하다. 다 만든 가격이 원래 가격보다 작은지 확인하는 작업은 숫자를 앞에서 부터 확인하면서 boolean형 값인 less를 사용하는 것이다. 만약 현재 만들어지고 있는 숫자가 원래 숫자의 해당 인덱스의 값보다 작은 경우는 앞으로 어떤 숫자를 선택하든 e보다 작으므로 그 정보를 전달하는 것이다. less가 false인 경우는 새로운 숫자를 선택할 때 해당 인덱스의 원래 숫자보다 작은 값만을 선택하면 된다.

이제 마지막으로 m의 배수인지 확인하는 작업을 살펴보자. m의 배수라는 것은 m으로 나눴을 때 0이라는 것이다. 특정 수를 m으로 나눈 나머지를 찾는 과정은 해당 수의 가장 큰 자릿수부터 나눠가면서 생기는 나머지를 그 다음 자리수로 이동시켜서 더이상 나누어질 수 없을 때까지 반복하는 것이다.
따라서 뒤에 오는 자릿수의 관점에서는 앞에 어떤 숫자가 오든 넘어오는 나머지만 같다면 최종 결과 값은 같아 지는 것이다. 따라서 이를 활용해 m의 나머지가 될 수 있는 0부터 m-1 까지의 값을 캐쉬의 인덱스로 활용할 수 있다.