2466. Count Ways To Build Good Strings

리트코드 2466번 풀이

문제

Count Ways To Build Good Strings

풀이

문제이해하기…

문자열을 만드는 프로세스 : (빈 문자열에서 시작한다)

1. “0”을 zero번 붙인다.
2. “1”을 one번 붙인다.

위 1, 2 중 하나를 여러 번 반복해서 문자열을 만든다.

좋은 문자열이란 위 프로세스로 만들어진 문자열 중에 길이가 low 이상 high 이하인 것.

이렇게 해서 서로 다른 좋은 문자열을 만드는 문제이다.

문제 풀기…

우선 점화식을 구해보자. 규칙을 찾기 위해서 zero = 1, one = 1로 놓고 생각해봤다.

길이가 정확히 i인 좋은 문자열을 구하는 경우의 수 = dp[i]

• dp[2] = 4 (‘00, 01, 10, 11’)
• dp[3] = 8 (‘000’, ‘001’, ‘010’, ‘100’, ‘011’, ‘101’, ‘110’, ‘111’)
• dp[n]은 dp[n-zero]에다가 0을 zero만큼 덧붙이는 경우와 dp[n-one]에다가 0을 one만큼 덧붙이는 경우의 합이다. (깨닫다…!)

점화식을 구했으니 초깃값을 결정해야 한다. low가 1부터 시작하니까 dp[0]은 구할 일이 없는 값인데, dp[1]을 구해보면

dp[1] = dp[0] + dp[0] = 2 (‘0’, ‘1’)

이므로 dp[0]은 1로 두자.

코드

function countGoodStrings(low: number, high: number, zero: number, one: number): number {
  const MOD = 10 ** 9 + 7;
  const dp = Array.from({ length: high + 1 }, () => 0);
  dp[0] = 1;
  let answer = 0;

  for (let i = 1; 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) answer = (answer + dp[i]) % MOD;
  }

  return answer;
}

시간 / 공간 복잡도

• 시간 복잡도: O(high)
• 공간 복잡도: O(high)

여담

dp는 뭔가 실력이 향상되는 것 같지 않고 그날 그날 컨디션에 따라서 잘 풀릴 때도 있고 안 풀릴 때도 있는 것 같다… 뭔가 깨달음을 얻는 느낌처럼 문제를 풀게 되는 듯… 그냥 자주 풀면 그 깨달음이 빨리 와서 잘 풀리게 되는 것 같기도 하다… 😩