LeetCode 1416. Restore The Array

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

Restore The Array - LeetCode

 

숫자의 일부분을 그룹으로 나누는 경우의 수를 구하는 문제!

 

근데 조건이 있다.

1. 각 그룹의 값이 0으로만 이루어지면 안된다.

2. 각 그룹의 값이 1이상 k이하 여야 한다.

 

[코드]

class Solution {
    public int mod = (int)1e9+7, N = 0;
    public int[] dp;
    public int numberOfArrays(String s, int k) {
        N = s.length();
        dp = new int[N+1];

        return dfs(0, s, k);
    }

    public int dfs(int idx, String s, int k){
        if(dp[idx]!=0)
            return dp[idx];
        
        if(idx == N)
            return 1;

        if(s.charAt(idx)=='0')
            return 0;

        int cnt = 0;

        for(int i = idx; i<N; i++){
            String str = s.substring(idx, i+1);

            if(Long.parseLong(str) > k)
                break;
            
            cnt = (cnt + dfs(i+1, s, k)) % mod;
        }

        dp[idx] = cnt;
        return cnt;
    }
}