텍스트 편집기에 'A' 문자가 하나만 있다고 가정합니다. 각 단계에 대해 이 문자에 대해 두 가지 작업을 수행할 수 있습니다.
- 모두 복사 - 메모장에 있는 모든 문자를 복사할 수 있습니다.
- 붙여넣기 - 지난번에 복사한 문자를 붙여넣을 수 있습니다.
이제 숫자 n이 있다고 가정합니다. 허용된 최소 단계 수를 수행하여 메모장에서 정확히 n 'A'를 얻어야 합니다. n 'A'를 얻으려면 최소 단계 수에서 결과를 찾아야 합니다. 따라서 주어진 n이 3이면 답은 3이 되므로 처음에는 "A"가 하나만 있습니다. 이제 이것을 복사하여 붙여넣으면 이제 "AA"가 됩니다. 이제 다시 붙여 넣을 수 있으므로 하나의 'A'가 배치됩니다. 따라서 우리는 "AAA"를 얻을 것입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- ret :=0
- 2~n
- 범위의 k에 대해
- n mod k가 0이 아닌 동안
- ret :=ret + k 및 n :=n / k
- n mod k가 0이 아닌 동안
- 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minSteps(int n) {
int ret = 0;
for(int k = 2; k <= n; k++){
for(; n % k == 0; ret += k, n /= k);
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.minSteps(10));
} 입력
10
출력
7