[LeetCode] 650. 2 Keys Keyboard

https://leetcode.com/problems/2-keys-keyboard/

2 Keys Keyboard - LeetCode

2 Keys Keyboard - Medium

 

 

화면에 A가 있고, 2가지 기능만 있는 키보드가 있다.

기능은 전체 복사와 붙여넣기 2가지이다.

이 때, A를 n개 출력한다고 할때, 키보드를 최소한 몇번눌러야 하는지 구하는 문제이다.

랜덤으로 돌린 문제인데, 신기하게 바로 직전에 풀었던 343. Integer Break 와 매우 비슷한 문제다.

https://kohsmos.tistory.com/107

[LeetCode] 343. Integer Break

 

처음에는 감이 안잡혀 하나씩 해보았다.

1 => 0 (동작X)

2 => 2 (복 붙 : 1X2)

3 => 3 (복 붙 붙 : 1X3)

4 => 4 (복 붙 복 붙 : 2X2 / 복 붙 붙 붙 : 1X4)

6 => 5 (복 붙 복 붙 붙 : 2X3 / 복 붙 붙 복 붙 : 3X2)

8 => 6 (복 붙 복 붙 복 붙 : 4X2 / 복 붙 복 붙 붙 붙 : 2X4)

24 => 9 (복 붙 복 붙 붙 붙 붙 붙 붙 ... : 2X12 / 복 붙 복 붙 복 붙 ... : 4X6 / 복 붙 복 붙 복 붙 복 붙 붙 : 8X3)

 

예시를 들기위해 많이 써보았다.

보면 기본적으로 n을 두가지 수의 곱으로 분해할 수 있고,

이 두 가지 수를 다시 문제에 넣어 구한 값들을 더하면 답이 된다.

소수의 경우에는 분해가 안되므로 1로 n번 해야하므로 n이 된다.

따라서 Integer break와는 반대로, 2부터 n까지 곱으로 나눈 뒤, 더해서 최소값이 되는 값을 찾아주자.

 

전체 풀이 코드

class Solution {
public:
    int minSteps(int n) {
        int m[1005];
        m[1] = 0;
        for (int i=2; i<=n; i++) {
            m[i] = i;
            for (int j=1; j<=sqrt(i); j++) if (i%j==0) m[i] = min(m[i], m[j]+m[i/j]);
        }
        return m[n];
    }
};