문제 개요
텍스트 편집기에 문자 'A'가 딱 하나만 있다고 가정해 보겠습니다. 우리는 매 단계마다 다음 두 가지 연산 중 하나를 수행할 수 있습니다.
- 모두 복사(Copy All) – 화면에 있는 모든 문자를 클립보드에 복사합니다.
- 붙여넣기(Paste) – 마지막으로 복사한 내용을 화면에 붙여넣습니다.
숫자 n이 주어졌을 때, 최소한의 연산 횟수로 화면에 정확히 n개의 'A'를 만들어야 합니다. 즉, n개의 'A'를 얻기 위해 필요한 최소 단계 수를 구하는 것이 이 문제의 목표입니다.
예시
n이 3이라면 답은 3입니다. 처음에는 'A'가 하나뿐이므로 먼저 복사하고 붙여넣어 "AA"를 만듭니다. 이후 한 번 더 붙여넣으면 'A'가 하나 추가되어 "AAA"가 됩니다. 이처럼 총 세 번의 연산으로 목표를 달성할 수 있습니다.
풀이 접근 방법
이 문제의 핵심은 소인수분해입니다. n개의 'A'를 만드는 최소 연산 횟수는 n의 소인수들의 합과 같습니다. 복사 후 붙여넣기를 반복하는 과정은 결국 현재 문자 수를 특정 인수의 배수로 늘리는 작업이기 때문입니다. 문자 수를 f배로 늘리려면 복사 1회와 붙여넣기 (f−1)회, 즉 f번의 연산이 필요합니다.
예를 들어 n = 10 = 2 × 5이므로, 2배로 만드는 데 2번, 5배로 만드는 데 5번, 총 7번의 연산이 필요합니다.
알고리즘 단계
- 결괏값 ret을 0으로 초기화합니다.
- k를 2부터 n까지 반복하면서, n이 k로 나누어 떨어지는 동안 ret에 k를 더하고 n을 k로 나눕니다.
- 모든 반복이 끝나면 ret을 반환합니다.
C++ 구현 예제
#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
코드 설명
minSteps 함수는 2부터 시작해 n을 나누어 떨어지게 하는 가장 작은 인수를 차례대로 찾아 ret에 누적합니다. 이 과정은 사실상 n을 소인수분해하는 것과 같으며, 각 소인수의 합이 곧 최소 연산 횟수가 됩니다. n = 10의 경우 10 = 2 × 5이므로 2 + 5 = 7이 출력됩니다. 이 알고리즘의 시간 복잡도는 O(√n) 수준으로 매우 효율적입니다.