LeetCode 2466. Count Ways To Build Good Strings(JAVA)

출처 : https://leetcode.com/problems/count-ways-to-build-good-strings/description/?envType=daily-question&envId=2024-12-30

 

#문제

Given the integers zero, one, low, and high, we can construct a string by starting with an empty string, and then at each step perform either of the following:
Append the character '0' zero times.Append the character '1' one times.
This can be performed any number of times.
A good string is a string constructed by the above process having a length between low and high (inclusive).
Return the number of different good strings that can be constructed satisfying these properties. Since the answer can be large, return it modulo 10^9 + 7.


정수 zero, one, low, high가 주어졌을 때, 다음 과정을 통해 문자열을 구성할 수 있습니다:
빈 문자열에서 시작합니다.각 단계에서 아래 두 가지 작업 중 하나를 수행할 수 있습니다:
문자 '0'을 zero번 추가합니다.
문자 '1'을 one번 추가합니다.
이 작업은 원하는 만큼 반복할 수 있습니다.

좋은 문자열은 위의 과정을 통해 구성된 문자열로, 길이가 low 이상 high 이하인 문자열을 의미합니다.
주어진 조건을 만족하는 좋은 문자열의 서로 다른 개수를 반환하세요. 결과가 매우 클 수 있으므로, 정답을 10⁹ + 7로 나눈 나머지를 반환하세요.

 

접근 : DFS + DP(Memoization)

문자열을 만든다는 함정에 빠지면 안됨, 길이를 만족하는 조합의 수를 구하는 문제임

즉 zero, one 의 조합으로 만들어진 문자열의 길이를  low 이상 hight 이하 만들수있는 경우의 수만 구하면 문제를 해결할수있음.

 

public class Solution {
    private int MOD = 1000000007;
    private int[] dp;
    public int countGoodStrings(int low, int high, int zero, int one) {
        dp = new int[high + 1];
        Arrays.fill(dp, -1);
        dp[high] = 1;
        return  dfs(zero,one,low,high,0);
    }
    //dp[sum]: 현재 길이가 sum일 때, 앞으로 조건 (low ≤ 길이 ≤ high)을 만족하는 문자열을 만들 수 있는 경우의 수
    private int dfs(int zero,int one,int low,int high,int sum){
        if(sum > high) return 0;
        if(dp[sum] != -1){// 이미 계산된 경우
        	return dp[sum];
        }
        dp[sum] = 0;
        if(sum >= low){
        	dp[sum]++;
        }
        //zero만큼 길이를 추가했을때의 유효한 경우의수
        dp[sum] = (dp[sum] + dfs(zero,one,low,high,sum+zero)) % MOD;
        //one만큼 길이를 추가했을때의 유효한 경우의수
        dp[sum] = (dp[sum] + dfs(zero,one,low,high,sum+one)) % MOD;

        return dp[sum];
    }
}