주어진 숫자를 만드는 데 필요한 최소 자릿수를 찾아야합니다. 예를 들어 : 14 => 95 (9 + 5 = 14)는 14를 형성하기위한 최소 인 두 자리입니다.
int moves(int n) {
int m = 0; // Minimum count
while (n-9 >= 0) { // To place maximum number of 9's
n -= 9;
m++;
}
if (n == 0) { // If only nines made up the number
return m;
}
else {
m++;
return m;
}
}
온라인 심사 위원이 TLE (런타임 제한 초과)를 받고 있습니다. 개선 할 수있는 방법 또는 더 나은 접근 방법이 있습니까?
코드는 9가 해당 숫자에 몇 번이나 들어가는 지 살펴 보는 것으로 시작합니다. 이것은 더 쉽게 수행 할 수 있습니다.
int m = n/9;
나머지는 버려지는 정수 나눗셈을하기 때문에 이것으로 충분합니다. 경우에주의 n할 것 float또는 다른 부동 유형이 작동하지 않을 것입니다.
남은 질문은 9로 나눌 수 있는지 여부입니다. 그렇지 않은 경우 하나의 추가 숫자가 있습니다. 이것은 모듈로 연산자에 의해 수행 될 수 있습니다 (이해하기 쉽도록 장황하게 만들었습니다) :
bool divisible_by_nine = (n % 9 == 0);
모듈로 연산자를 모를 수 있다고 가정하면 정수 나눗셈의 나머지, 47/9 = 5 나머지 2이므로 47 % 9 = 2를 반환합니다.
그것 없이는 함께 갈 것입니다
int remainder = n - 9*m;
bool divisible = (remainder == 0);
결합 :
int required_digits(int number)
{
bool divisible = (number % 9 == 0);
return number/9 + (divisible ? 0 : 1);
}
또는 원하는 정도에 따라 한 줄로 표시합니다.
int required_digits(int number)
{
return number/9 + (number % 9 == 0 ? 0 : 1);
}
루프가 없기 때문에 Θ (1)에 있으므로 필요한 시간 제한에서 작동합니다.
(기술적으로는 프로세서가 내부적으로 수행 한 것처럼 분할을 처리하는 것이 좋지만 매우 효율적입니다. 절대적으로 정확하려면 "분할이 일정한 시간 작업이라고 가정"을 추가해야합니다.)
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다