[LeetCode] 651 - 4 Keys Keyboard

문제

• 링크: https://leetcode.com/problems/4-keys-keyboard
• 난이도: Medium
• 태그: 다이나믹 프로그래밍
• 결과: Time: 0 ms (100%), Space: 7.9 MB (89.59%)

풀이

class Solution {
public:
    int maxA(int n) {
        int dp[51];
        dp[0] = 0;
        for (int i = 1; i <= n; ++i)
        {
            dp[i] = dp[i - 1] + 1;
            for (int j = 1; j <= i - 3; ++j)
            {
                int cur = dp[i - j - 2] * (j + 1);
                dp[i] = max(cur, dp[i]);
            }
        }

        return dp[n];
    }
};

문제 자체는 백준에서 본 문제랑 동일했다. 문제 이름까지 정확히 기억했는데, 크리보드다. 사실 이미 풀었던 문제라서 바로 풀었던 건 아니고, 좀 애를 먹다가 결국 예전에 짠 코드를 참고했다.

점화식 세우기

일단 그냥 출력하는 경우는 d[i - 1] + 1로 간단하게 구할 수 있다. 전체 선택 - 복사 - 붙여넣기는 d[i - 3] * 2까지는 쉽게 생각했는데 그 다음 또 붙여넣기를 누르는 경우를 어떻게 처리해야하는지 헤맸다.

조금만 더 일반화 과정을 거치면 됐다.

• 선택 - 복사 - 붙여넣기: d[i - 3] * 2
• 한번 더 붙여넣기: d[i - 4] * 3
• 한번 더 붙여넣기: d[i - 5] * 4
• …
• j번 붙여넣기: d[i - (j + 2)] * (j + 1)

그리고 j에 대해서도 반복문을 돌리면서 계산하면 풀이는 끝난다.

배운 점과 후기

아무래도 DP 문제는 항상 어렵게 느껴진다. 점화식 세우는 패턴을 많이 봐둬야 익숙해진다고 들은적이 있어서 DP 문제도 더 적극적으로 찾아서 풀어야겠다.

잡담

이건 Weekly Premium이라서 풀었다. 개중에서도 W2, 그러니까 2주차 문제였는데 이미 지난 문제는 풀어도 인정이 안되는 거였다. 그래서 풀고 나서도 빨간 점이 남아있다…