ปัญหา 2 Keys Keyboard ใน C++

มีตัวอักษร 'A' อยู่ใน notepad เพียงตัวเดียว สามารถทำ 2 การดำเนินการ:

• Copy All: คัดลอกตัวอักษรทั้งหมดบน notepad
• Paste: วางตัวอักษรที่คัดลอกไว้ล่าสุด

ต้องการให้ได้ 'A' ทั้งหมด n ตัว โดยใช้จำนวนขั้นตอนน้อยที่สุด หาจำนวนขั้นตอนขั้นต่ำ

ตัวอย่าง: n = 3 → 3 ขั้นตอน (เริ่ม A → Copy → Paste ได้ AA → Paste อีกครั้งได้ AAA)

วิธีแก้ปัญหา (Prime Factorization)

จำนวนขั้นตอนน้อยที่สุด = ผลรวมของเฉพาะตัวประกอบของ n

1. ret = 0
2. วน k = 2 ถึง n:
   • while n หาร k ลงตัว: ret += k, n /= k
3. คืนค่า 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;
    }
};

int main() {
    Solution ob;
    cout << ob.minSteps(10);
    return 0;
}

Input

10

Output

7