2466. Count Ways To Build Good Strings

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

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:04:21

 

---

 

문제 설명

 

zero, one, low, high 정수가 주어질 때, 우리는 빈 문자열에서 시작하여 문자열을 만들 수 있으며,각 단계에서 둘 중 하나를 수행한다.

 

* '0' 문자를 zero번 반복해서 추가한다.

* '1' 문자를 one번 반복해서 추가한다.

 

이 작업은 몇 번이고 수행될 수 있다.

좋은 문자열은, 위의 작업으로 구성된 문자열이 low, high 사이의 길이(경계 포함)를 가졌을 때의 문자열이다.

이 조건을 만족하는 서로 다른 좋은 문자열의 개수를 구하여라, 값이 매우 클 수 있으므로, 10^9 + 7을 모듈로 연산한 결과를 반환하라.

---

 

풀이

 

바로 DP로 풀어보자.

DP[i] = DP[i - ones] + DP[i - zeros]

가 성립한다. (재귀적으로 두 수행 방식 - '1'을 붙이거나 '0'을 붙이는 방식 - 이 서로의 단계에 영향을 끼치지 않고 수행될 수 있다)

 

즉 O(N)의 시간복잡도 및 공간복잡도 내에 문제를 빠르게 풀 수 있겠다.

 

풀이 코드

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        mod = 10 ** 9 + 7
        dp = [0]*(high+1)
        dp[0] = 1
        ans = 0

        for i in range(min(zero, one), high+1):
            if i - zero >= 0 :
                dp[i] = (dp[i-zero] + dp[i]) % mod
            if i - one >= 0 :
                dp[i] = (dp[i-one] + dp[i]) % mod
            if i >= low :
                ans = (ans + dp[i]) % mod
        return ans