문제 링크

내 코드

MLE.. $\rightarrow$ Solution 참고.

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        for(int i{};i<zero;++i) {
            zeros.push_back('0');
        }
        for(int i{};i<one;++i) {
            ones.push_back('1');
        }
        l = low, h = high;

        makeString("");
        return answer;
    }
private:
    int answer{};
    string zeros, ones;
    int l, h;
    void makeString(string curr) {
        if(l <= curr.size()) {
            ++answer;
        }
        if(curr.size() + zeros.size() <= h) makeString(curr + zeros);
        if(curr.size() + ones.size() <= h) makeString(curr + ones);
    }
};

Solution

Approach 1: Dynamic Programming (Iterative).

• 4ms, 11.70MB
• Complexity
  • Time Complexity: $O(high)$
  • Space Complexity: $O(high)$

// Java Code -> C++ Code
class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        // dp[i]는 길이가 i인 좋은 문자열의 수를 저장
        vector<int> dp(high + 1, 0);
        dp[0] = 1; // 길이가 0인 문자열의 수는 1
        const int mod = 1'000'000'007;

        // 각 길이 `end`에 대해 반복
        for (int end = 1; end <= high; ++end) {
            // 현재 문자열을 0 `zero`개 또는 1 `one`개로 만들 수 있는지 확인
            if (end >= zero) {
                dp[end] += dp[end - zero];
            }
            if (end >= one) {
                dp[end] += dp[end - one];
            }
            dp[end] %= mod;
        }

        // 유효한 길이 [low ~ high]의 문자열 수를 합산
        int answer = 0;
        for (int i = low; i <= high; ++i) {
            answer += dp[i];
            answer %= mod;
        }
        return answer;
    }
};

GPT

이 코드는 주어진 제약 조건에 따라 “좋은 문자열”을 생성할 수 있는 방법의 수를 계산합니다. “좋은 문자열”은 $0$과 $1$을 사용하여 구성되며, 특정 개수의 $0$ 또는 $1$을 더하여 생성됩니다. 이 문제는 동적 프로그래밍(DP) 을 사용해 해결합니다.

---

문제 정의

주어진 조건

1. $low$: “좋은 문자열”의 최소 길이.
2. $high$: “좋은 문자열”의 최대 길이.
3. $zero$: 문자열 끝에 $zero$ 개의 $0$을 추가 가능.
4. $one$: 문자열 끝에 $one$ 개의 $1$을 추가 가능.

목표

• 길이가 $[low, high]$인 “좋은 문자열”의 총 개수를 계산합니다.
• 결과를 $10^9 + 7$로 나눈 나머지를 반환합니다.

---

코드 설명

1. DP 배열 초기화

vector<int> dp(high + 1, 0);
dp[0] = 1; // 길이가 0인 문자열의 수는 1

• dp[i]: 길이가 $i$인 “좋은 문자열”의 수를 저장.
• 길이가 $0$인 문자열은 유일하므로 초기값 $dp[0] = 1$.

---

2. DP 점화식

for (int end = 1; end <= high; ++end) {
    if (end >= zero) {
        dp[end] += dp[end - zero];
    }
    if (end >= one) {
        dp[end] += dp[end - one];
    }
    dp[end] %= mod;
}

• $end$: 현재 계산 중인 문자열의 길이.
• 점화식:
  1. $end \geq zero$인 경우:
     • 끝에 $zero$개의 $0$을 추가하여 길이 $end$ 문자열을 생성.
     • $dp[end] += dp[end - zero]$.
  2. $end \geq one$인 경우:
     • 끝에 $one$개의 $1$을 추가하여 길이 $end$ 문자열을 생성.
     • $dp[end] += dp[end - one]$.
  3. $mod$로 나머지를 구해 오버플로우를 방지.

---

3. 유효한 길이의 합산

int answer = 0;
for (int i = low; i <= high; ++i) {
    answer += dp[i];
    answer %= mod;
}

• 길이가 $[low, high]$인 문자열의 수를 합산.
• $mod$로 나머지를 구해 최종 결과를 계산.

---

시간 및 공간 복잡도

시간 복잡도

1. DP 배열 계산:
   • $O(high)$: 각 $end \in [1, high]$에 대해 반복.
2. 결과 합산:
   • $O(high - low)$: $[low, high]$ 범위의 합산.

총 시간 복잡도: $O(high)$.

공간 복잡도

• DP 배열: $O(high + 1)$.

---

작동 예시

입력:

low = 3, high = 3, zero = 1, one = 2

계산 과정:

1. 초기화: $dp = [1, 0, 0, 0]$

2. DP 배열 채우기:

   • $end = 1$: $dp[1] = dp[1 - 1] = 1$.
     $dp = [1, 1, 0, 0]$.
   • $end = 2$: $dp[2] = dp[2 - 1] + dp[2 - 2] = 1 + 1 = 2$.
     $dp = [1, 1, 2, 0]$.
   • $end = 3$: $dp[3] = dp[3 - 1] + dp[3 - 2] = 2 + 1 = 3$.
     $dp = [1, 1, 2, 3]$.

3. 결과 합산:

   • 길이 $3$만 포함하므로 $answer = dp[3] = 3$.

출력:

3

---

확장 예시

입력:

low = 2, high = 4, zero = 1, one = 2

계산 과정:

1. 초기화: $dp = [1, 0, 0, 0, 0]$

2. DP 배열 채우기:

   • $end = 1$: $dp[1] = dp[1 - 1] = 1$.
     $dp = [1, 1, 0, 0, 0]$.
   • $end = 2$: $dp[2] = dp[2 - 1] + dp[2 - 2] = 1 + 1 = 2$.
     $dp = [1, 1, 2, 0, 0]$.
   • $end = 3$: $dp[3] = dp[3 - 1] + dp[3 - 2] = 2 + 1 = 3$.
     $dp = [1, 1, 2, 3, 0]$.
   • $end = 4$: $dp[4] = dp[4 - 1] + dp[4 - 2] = 3 + 2 = 5$.
     $dp = [1, 1, 2, 3, 5]$.

3. 결과 합산:

   • $answer = dp[2] + dp[3] + dp[4] = 2 + 3 + 5 = 10$.

출력:

10

Approach 2: Dynamic Programming (Recursive)

• 7ms, 14.82MB
• Complexity
  • Time Complexity: $O(high)$
  • Space Complexity: $O(high)$

// Java Code -> C++ Code
class Solution {
private:
    vector<int> dp;
    const int mod = 1'000'000'007;

    // 길이가 `end`인 좋은 문자열의 수를 계산
    int dfs(int end, int zero, int one) {
        if (dp[end] != -1) 
            return dp[end];
        
        int count = 0;
        if (end >= one) {
            count += dfs(end - one, zero, one);
        }
        if (end >= zero) {
            count += dfs(end - zero, zero, one);
        }
        dp[end] = count % mod;
        return dp[end];
    }

public:
    int countGoodStrings(int low, int high, int zero, int one) {
        dp.resize(high + 1, -1);
        dp[0] = 1;

        // 유효한 길이 [low ~ high]의 문자열 수를 합산
        int answer = 0;
        for (int end = low; end <= high; ++end) {
            answer += dfs(end, zero, one);
            answer %= mod;
        }
        return answer;
    }
};

GPT

이 코드는 재귀와 메모이제이션을 사용하여 “좋은 문자열”의 개수를 계산합니다. 각 문자열의 길이에 대해 가능한 모든 조합을 탐색하며, 이미 계산한 값을 메모이제이션하여 중복 계산을 방지합니다. 이 접근 방식은 효율적이며, $O(\text{high})$ 시간 복잡도를 가집니다.

---

문제 정의

1. 주어진 조건:

   • $low$: “좋은 문자열”의 최소 길이.
   • $high$: “좋은 문자열”의 최대 길이.
   • $zero$: 끝에 $zero$개의 $0$을 추가 가능.
   • $one$: 끝에 $one$개의 $1$을 추가 가능.

2. 목표:

   • 길이가 $[low, high]$인 “좋은 문자열”의 총 개수를 계산.
   • 결과를 $10^9 + 7$로 나눈 나머지를 반환.

---

코드 분석

1. 주요 아이디어

• 재귀와 메모이제이션:
  • dfs(end): 길이가 $end$인 문자열의 개수를 계산.
  • 이미 계산된 값은 dp[end]에 저장하여 중복 계산 방지.
• 점화식:
  • 길이가 $end$인 문자열은 다음 두 가지 방법으로 생성 가능:
    1. $end \geq one$: $end - one$ 길이의 문자열 뒤에 $one$개의 $1$ 추가.
    2. $end \geq zero$: $end - zero$ 길이의 문자열 뒤에 $zero$개의 $0$ 추가.

---

2. 코드 단계별 설명

1. DP 배열 초기화

dp.resize(high + 1, -1);
dp[0] = 1;

• dp[end]: 길이가 $end$인 문자열의 개수를 저장.
• $dp[0] = 1$: 길이가 $0$인 문자열은 유일.

---

2. DFS 함수

int dfs(int end, int zero, int one) {
    if (dp[end] != -1) 
        return dp[end];
    
    int count = 0;
    if (end >= one) {
        count += dfs(end - one, zero, one);
    }
    if (end >= zero) {
        count += dfs(end - zero, zero, one);
    }
    dp[end] = count % mod;
    return dp[end];
}

1. 기저 조건:

   • dp[end] != -1: 이미 계산된 값이 있으면 반환하여 중복 계산 방지.

2. 점화식:

   • $end \geq one$: $dfs(end - one)$ 호출.
   • $end \geq zero$: $dfs(end - zero)$ 호출.

3. 결과 저장:

   • $dp[end] = (count \mod \text{mod})$.

---

3. 유효 길이 합산

int answer = 0;
for (int end = low; end <= high; ++end) {
    answer += dfs(end, zero, one);
    answer %= mod;
}

• 길이가 $[low, high]$인 모든 문자열의 개수를 합산.
• $mod$ 연산으로 결과를 제한.

---

시간 및 공간 복잡도

시간 복잡도

1. DFS 계산:
   • 각 $end \in [0, high]$에 대해 한 번 계산 ($O(high)$).
2. 결과 합산:
   • $[low, high]$ 범위 합산 ($O(high - low)$).

총 시간 복잡도:
$O(high)$

공간 복잡도

1. DP 배열:
   • $O(high + 1)$.
2. 재귀 호출 스택:
   • 최대 깊이: $O(high / \min(zero, one))$.

총 공간 복잡도:
$O(high)$

---

작동 예시

입력:

low = 3, high = 3, zero = 1, one = 2

계산 과정:

1. 초기화: $dp = [-1, -1, -1, -1], dp[0] = 1$

2. DFS 호출:

   • $dfs(3)$:
     • $dfs(2) + dfs(1)$.
   • $dfs(2)$:
     • $dfs(1) + dfs(0)$.
   • $dfs(1)$:
     • $dfs(0)$.
   • $dfs(0)$:
     • 반환 $1$.

3. 결과: $dp = [1, 1, 2, 3]$

4. 합산:

   • $answer = dp[3] = 3$.

출력:

3

---

확장 예시

입력:

low = 2, high = 4, zero = 1, one = 2

계산 과정:

1. 초기화: $dp = [-1, -1, -1, -1, -1], dp[0] = 1$

2. DFS 호출:

   • $dfs(4)$, $dfs(3)$, $dfs(2)$.

3. 결과: $dp = [1, 1, 2, 3, 5]$

4. 합산:

   • $answer = dp[2] + dp[3] + dp[4] = 2 + 3 + 5 = 10$.

출력:

10