자릿수 DP (Digit DP)

정의

자릿수 DP (Digit DP) 는 [0, N] 범위 또는 [L, R] 구간에서 조건을 만족하는 정수의 개수를 세는 DP 기법. 각 자릿수를 순차적으로 선택하며, “현재까지 upper bound 에 tight 한지” 같은 상태를 추적.

대표 문제: “각 자리 합이 K”, “특정 숫자 미포함”, “회문 수”, “오름차순 자릿수” 같은 조건 카운팅.

문제 상황과 동기

“1 부터 N 까지 중, 각 자리 수의 합이 K 인 수의 개수” 를 구하려면:

• naive: N 까지 모두 순회, 각 자릿수 합 계산. O(N × log N). N = 10^18 이면 불가능.
• digit DP: 각 자릿수를 선택하는 DP. 상태 = (자릿수 위치, tight 여부, 지금까지 합). O(D × K) (D = 자릿수 길이). D ≤ 20, K ≤ 200 정도면 즉시.

핵심 통찰: 수를 왼쪽(최고 자리)부터 순차 선택하면, “upper bound 를 넘지 않으면서” 조건을 만족하는 수의 개수를 DP 로 세기 가능. tight 플래그로 bound 관리.

자주 등장하는 컨텍스트:

• PS: “1~N 중 조건 만족 수 카운팅” (N ≤ 10^18)
• 실무: 숫자 규칙 필터링, 통계 집계

시각화

핵심 아이디어

기본 패턴 (0 부터 N 까지 조건 만족 수 카운팅):

1. N 을 자릿수 배열 d[0..L-1] 로 변환 (d[0] = 최고 자리).
2. dp[pos][tight][state] = pos 번째 자릿수까지 선택했고, tight 상태이며, 조건 상태가 state 일 때 가능한 수의 개수.
3. tight = true: 현재까지 N 의 자릿수와 정확히 같음. 다음 자릿수는 0 ~ d[pos] 까지.
4. tight = false: 이미 N 보다 작음 확정. 다음 자릿수는 0 ~ 9.
5. 답: dp[0][true][초기 state].

전이:

dp[pos][tight][state]:
    if pos == L: return 1 if valid(state) else 0
    limit = d[pos] if tight else 9
    res = 0
    for digit in 0..limit:
        new_tight = tight and (digit == d[pos])
        new_state = update(state, digit)
        res += dp[pos + 1][new_tight][new_state]
    return res

[L, R] 구간 카운팅:

count(L, R) = count(0, R) - count(0, L - 1)

알고리즘

자릿수 합이 K 인 수의 개수 (0 ~ N):

digit_dp(N, K):
    d = digits(N)  // d[0] = 최고 자리
    L = len(d)
    memo = {}

    def dp(pos, tight, sum):
        if pos == L:
            return 1 if sum == K else 0
        if (pos, tight, sum) in memo:
            return memo[(pos, tight, sum)]

        limit = d[pos] if tight else 9
        res = 0
        for digit in 0..limit:
            new_tight = tight and (digit == d[pos])
            res += dp(pos + 1, new_tight, sum + digit)

        memo[(pos, tight, sum)] = res
        return res

    return dp(0, True, 0)

구현

// 자릿수 합이 K 인 수의 개수 (0 ~ N)
#include <bits/stdc++.h>
using namespace std;
​
long long N, K;
vector<int> d;
map<tuple<int, bool, int>, long long> memo;
​
long long dp(int pos, bool tight, int sum) {
  if (pos == (int)d.size())
      return (sum == K) ? 1 : 0;
​
  auto key = make_tuple(pos, tight, sum);
  if (memo.count(key)) return memo[key];
​
  int limit = tight ? d[pos] : 9;
  long long res = 0;
  for (int digit = 0; digit <= limit; digit++) {
      bool new_tight = tight && (digit == d[pos]);
      res += dp(pos + 1, new_tight, sum + digit);
  }
​
  return memo[key] = res;
}
​
int main() {
  cin >> N >> K;
  // N 을 자릿수 배열로
  string s = to_string(N);
  for (char c : s) d.push_back(c - '0');
​
  cout << dp(0, true, 0) << "\n";
}

# 자릿수 합이 K 인 수의 개수 (0 ~ N)
import sys
from functools import lru_cache
input = sys.stdin.readline
​
N, K = map(int, input().split())
d = [int(x) for x in str(N)]  # 자릿수 배열
​
@lru_cache(maxsize=None)
def dp(pos, tight, total):
  if pos == len(d):
      return 1 if total == K else 0
​
  limit = d[pos] if tight else 9
  res = 0
  for digit in range(limit + 1):
      new_tight = tight and (digit == d[pos])
      res += dp(pos + 1, new_tight, total + digit)
  return res
​
print(dp(0, True, 0))

// 자릿수 합이 K 인 수의 개수 (0 ~ N)
import java.util.*;
import java.io.*;
​
public class Main {
  static long N;
  static int K;
  static int[] d;
  static Map<String, Long> memo = new HashMap<>();
​
  static long dp(int pos, boolean tight, int sum) {
      if (pos == d.length)
          return (sum == K) ? 1 : 0;
​
      String key = pos + "," + tight + "," + sum;
      if (memo.containsKey(key)) return memo.get(key);
​
      int limit = tight ? d[pos] : 9;
      long res = 0;
      for (int digit = 0; digit <= limit; digit++) {
          boolean newTight = tight && (digit == d[pos]);
          res += dp(pos + 1, newTight, sum + digit);
      }
​
      memo.put(key, res);
      return res;
  }
​
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      N = Long.parseLong(st.nextToken());
      K = Integer.parseInt(st.nextToken());
​
      String s = Long.toString(N);
      d = new int[s.length()];
      for (int i = 0; i < s.length(); i++)
          d[i] = s.charAt(i) - '0';
​
      System.out.println(dp(0, true, 0));
  }
}

20 5

2

100 10

4

복잡도

자릿수 합 문제 예시:

• D = 20 (10^18 의 길이)
• S = 200 (최대 합 9 × 20 = 180)
• 상태 개수: 20 × 2 × 200 = 8,000, 즉시 계산 가능

변형 / 활용

1. [L, R] 구간 카운팅

long long count_range(long long L, long long R, int K) {
    return digit_dp(R, K) - digit_dp(L - 1, K);
}

2. 특정 숫자 금지

예: “4 또는 7 이 들어가지 않는 수”

for (int digit = 0; digit <= limit; digit++) {
    if (digit == 4 || digit == 7) continue;
    // 전이
}

3. 회문 수 카운팅

state = (앞에서 선택한 자릿수 배열), 뒤에서부터 확인.

4. 오름차순 자릿수

state = (이전 자릿수), 다음은 prev_digit 이상만 선택.

5. 소수 개수 (자릿수 제약)

각 자릿수 선택 후 최종 수가 소수인지 판별 (작은 N 에만 적용).

함정

1. leading zero 처리

“0123” 은 123 과 같음. leading zero 를 세지 않으려면 started 플래그 추가:

bool started = (sum > 0) || (digit > 0);

2. tight 플래그 실수

tight 는 “현재까지 upper bound 와 같은지”. 한 번이라도 작은 자릿수를 선택하면 tight = false 로 전환되어 유지.

3. [L, R] 에서 L-1 음수

L = 0 일 때 digit_dp(-1, K) 는 의미 없음. L = 0 이면 count(R) - 0.

4. 상태 설계 누락

문제 조건에 따라 state 가 복잡해짐. “이전 자릿수”, “특정 숫자 등장 여부”, “모듈로 나머지” 등을 모두 상태에 포함해야 중복 카운팅 방지.

BOJ 연습 문제

참고

• 동적 계획법
• 조합론 카운팅
• 메모이제이션