Daily LeetCode Challenge - 2466. Count Ways To Build Good Strings

Problem From.

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

오늘 문제는 주어진 규칙에 따라 글자를 만들었을때, low 와 high 사이의 길이를 가진 문자를 만들수 있는 최대의 갯수를 구하는 문제였다.

규칙은 다음과 같은데, 빈 문자열로 시작하여 각각의 스텝에서 0 을 zero 번 더하던가 1을 one 번 더해야 했다.
이 문제는 DP 로 풀 수 있었는데, memo 배열을 선언해두고, 각각의 memo 배열 칸에 각 스텝별로 들어갈 수 있는 zero 와 one 의 갯수 만큼 index 를 더해서 memo 배열에 저장해둔다. 예를 들면 memo[2] 에 2가 저장되어있고 0을 3번 더해서 memo[5] 를 만든다고 할때, memo[5] 는 memo[2] 를 만드는 경우의 수 2 + 1 이 되는 식이다.
위 방법을 high 에 도달할때까지 반복한다음 low 부터 high 까지의 memo 안에 저장되어있는 수를 모두 더해서 반환하면 되었다.

class Solution {
    fun countGoodStrings(low: Int, high: Int, zero: Int, one: Int): Int {
        
        val memo = Array(high + 1) { 0 }
        
        val min = Math.min(zero, one)
        
        val mod = 1000000007
        
        memo[0] = 1
        
        for(i in min..high) {
            
            if(i >= zero) {
                memo[i] = (memo[i] + memo[i - zero]) % mod
            }
            if(i >= one) {
                memo[i] = (memo[i] + memo[i - one]) % mod
            }
            
        }
        
        var sum = 0
        for(i in low..high) {
            sum = (sum + memo[i]) % mod
        }
        
        return sum
    }
}