[LeetCode] 650. 2 Keys Keyboard

 

https://leetcode.com/problems/2-keys-keyboard/solutions/?envType=daily-question&envId=2024-08-19

leetcode - 2 Keys Keyboard

문제 유형 : 다이나믹 프로그래밍, 재귀, 수학

문제 난이도 : Medium

 

문제

There is only one character 'A' on the screen of a notepad. You can perform one of two operations on this notepad for each step:

• Copy All: You can copy all the characters present on the screen (a partial copy is not allowed).
• Paste: You can paste the characters which are copied last time.

Given an integer n, return the minimum number of operations to get the character 'A' exactly n times on the screen.

 

노드패드에 글자 'A'만이 있다.

두 연산만들 할 수 있다.

모두 복사하기: 노드패드의 모든 글자를 복사한다(부분적 복사는 불가능하다.)

붙여넣기: 마지막에 복사한 것을 붙여넣을 수 있다

 

정수 n이 주어진다. A를 정확히 n번 화면에 띄우도록 필요한 최소 연산을 구하시오.

 

풀이

dp[i]를 'A' * i의 문자열을 만들기 위한 최소 연산횟수라 하자. 기저 사례로, dp[1] = 0, dp[0] = 0으로 해두자. 물론 dp[0]을 호출할 일은 없지만.

 

우선, 소수는 무조건 자기자신의 수만큼 연산해야 한다.

1을 복사 후, n-1붙여넣는 경우밖에 없으므로 , n이 소수라면, n회이다.

 

합성수는, 이전 약수들을 기반으로 계산해서 대조해보아야 한다.

약수들을 구해서, dp[약수] + 짝이 되는 약수(즉, N / 약수)를 계속 구해서 최소값을 업데이트해야 한다.

최종적으로 남은 최소값이 dp[i]가 되는 것이다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
private:
    vector<int> dp;
    set<int> primes;
public:
    set<int> get_divisors(int n) {
        set<int> res;
        for(int i = 2; i <= n/2; i++) {
            if(n % i == 0) {
                res.insert(i);
            }
        }
        return res;
    }
    int solve(int n) {
        if(dp[n] != -1) return dp[n];
        if(primes.find(n) != primes.end()) return dp[n] = n;

        auto divisors = get_divisors(n);
        int res = INT_MAX;
        
        for(auto &divisor : divisors) {
            res = min(res, solve(n / divisor) + divisor);
            res = min(res, solve(divisor) + n / divisor);
        }

        return dp[n] = res;
    }

    bool isPrime(int x) {
        for(int i = 2; i <= sqrt(x); i++) {
            if(x % i == 0) return false;
        }
        return true;
    }

    int minSteps(int n) {
        for(int i = 2; i <= n; i++) {
            if(isPrime(i)) primes.insert(i);
        }
        dp.resize(n+1, -1);
        dp[0] = 0;
        dp[1] = 0;

        return solve(n);
    }
};