1416. Restore The Array

[zeikar]

Problem link

https://leetcode.com/problems/restore-the-array/

Problem Summary

문자열과 k 가 주어진다. k까지의 수를 사용해서 문자열을 나눌 수 있는 경우의 수를 구하는 문제.

Solution

딱 보니 간단한 DP 같아서 풀었는데 메모리 초과가 많이 났다... modular 연산을 맨 마지막에 했는데 함수에서 리턴할때 넣어주니 돌아간다... 파이썬이 정수 범위가 없다지만 내부적으론 메모리를 더 쓰기 때문에 메모리가 터졌다

암튼 DP는 간단하다. DP[i] = i 인덱스부터 문자열의 경우의 수. 그러면 현재부터 k 를 넘지 않을 때까지 죽 돌면서 잘라주면서 체크하면 된다.
0으로 시작할 수 없으니 제외해주면 된다.

처음엔 자른 개수도 DP 매개변수로 받았지만 이게 더 깔끔한듯? (사실 메모리도 적게 먹긴 하다)

Source Code

from functools import lru_cache


class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:

        @lru_cache(None)
        def solve(idx: int):
            if idx == len(s):
                return 1
            if s[idx] == '0':
                return 0

            ret = 0
            for i in range(idx, len(s)):
                value = int(s[idx:i + 1])

                if value > k:
                    break

                ret += solve(i + 1)

            return ret % (10 ** 9 + 7)

        return solve(0)