[LeetCode] 2466. Count Ways To Build Good Strings

https://leetcode.com/problems/count-ways-to-build-good-strings/

Count Ways To Build Good Strings - LeetCode

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Medium

 

문제

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]의 범위에 들어오는 문자열의 개수를 구하여라.

 

 

풀이

우선, high +1 크기의 dp테이블을 만들어준다. dp[i]는 규칙대로 만들 수 있는 길이가 i인 문자열의 개수이다.

dp[0]은 ""의 빈 문자열로 1개 있다는 뜻으로 dp[0]은 1이다.

i == 1부터는 zero, one, low와 비교한다.

zero보다 크면, 문자열에 zero개의 '0'을 넣는다는 뜻으로, dp[i]에서 '0'을 zero개 추가시키기 전인dp[i-zero]를 누적시킨다.

one의 경우도 똑같다. one개의 '1'을 넣는 뜻으로, dp[i]에서 one개 추가시키기 전인dp[i-one]를 누적시킨다.

low보다 커지면 good string의 조건이 만족되므로 dp[i]를 ans에 누적시킨다.

i가 최대 good string의 길이의 high가 되기까지 반복한다.

 

코드(C++)

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        int mod = 1e9 + 7;
        vector<int> dp (high + 1);
        int ans = 0;
        dp[0] = 1;

        for(int i = 0; i <= high; i++){
            if(i >= zero){
                dp[i] += (dp[i] + dp[i-zero]) % mod;
            }
            if(i >= one){
                dp[i] = (dp[i] + dp[i-one]) % mod;
            }
            if(i >= low){
                ans = (ans + dp[i]) % mod;
            }
        }
        return ans;
    }
};