숫자로만 이루어진 문자열 s와 정수 k가 주어졌을 때, 문자열 s를 [1, k] 범위에 속하는 숫자들의 목록으로 나눌 수 있는 서로 다른 방법의 개수를 구하는 문제입니다. 답이 매우 커질 수 있으므로 결과는 10^9 + 7로 나눈 나머지를 반환합니다.
문제 예시
예를 들어 s = "3456", k = 500이 입력으로 주어지면 출력은 7이 됩니다. 다음과 같은 7가지 방법으로 문자열을 분할할 수 있기 때문입니다.
- [3, 4, 5, 6]
- [34, 5, 6]
- [3, 4, 56]
- [3, 45, 6]
- [34, 56]
- [345, 6]
- [3, 456]
풀이 접근 방식 (동적 계획법)
이 문제는 동적 계획법(DP)을 사용하면 효율적으로 해결할 수 있습니다. dp[i]를 "i번째 위치부터 문자열 끝까지 분할하는 방법의 수"로 정의하고, 뒤에서 앞으로 거꾸로 채워나갑니다.
알고리즘 단계
- m := 10^9 + 7 (결과를 나눌 모듈러 값)
- N := 문자열 s의 길이
- dp := 크기가 (N + 1)인 리스트를 생성하고 0으로 초기화
- dp[N] := 1 (빈 문자열을 분할하는 방법은 1가지)
- i를 N-1부터 0까지 감소시키며 반복:
- curr_val := 0으로 초기화
- j를 i부터 N-1까지 반복:
- curr_val := curr_val * 10 + int(s[j]) — 현재 위치에서 시작하는 숫자 값을 확장
- 만약 curr_val이 1 이상 k 이하라면:
- dp[i] := (dp[i] + dp[j + 1]) mod m
- 그렇지 않으면:
- 반복문 탈출 (값이 k를 초과하면 더 확장할 필요 없음)
- dp[0] 반환
핵심 아이디어는 각 위치 i에서 시작하는 부분 문자열을 하나씩 늘려가며 확인하고, 그 값이 [1, k] 범위 안에 있을 때만 다음 위치의 분할 방법 수(dp[j + 1])를 더한다는 것입니다. 값이 k를 초과하는 순간 더 이상 확장해도 범위를 벗어나므로 반복문을 종료해 시간을 절약합니다.
Python 구현 예제
class Solution: def solve(self, s, k): m = 10 ** 9 + 7 N = len(s) dp = [0] * (N + 1) dp[N] = 1 for i in range(N - 1, -1, -1): curr_val = 0 for j in range(i, N): curr_val = curr_val * 10 + int(s[j]) if 1 <= curr_val <= k: dp[i] = (dp[i] + dp[j + 1]) % m else: break return dp[0] ob = Solution() s = "3456" k = 500 print(ob.solve(s, k))
입력
"3456", 500
출력
7
복잡도 분석
시간 복잡도는 최악의 경우 O(N²)이지만, curr_val이 k를 초과하면 즉시 반복문을 종료하므로 실제로는 k의 자릿수에 따라 내부 반복이 제한되어 훨씬 빠르게 동작합니다. 공간 복잡도는 dp 배열을 위해 O(N)입니다.