Digit Dyanmic Programming

Digit Dynamic Programming & Back Tracking

자연수의 자리수에 관련된 어떠한 정보들을 저장하며 DP를 사용하거나 Back tracking을 활용하는 문제들이 있다.

주로 난이도가 Solved.ac 기준 플레티넘 상위권에 기록될 정도로 알고도 테크닉이 익숙하지 않다면 쉽게 풀 수 없는 수준이다.

약간 올드한 스타일의 DP긴 하다.

대략 다음과 같은 식으로 문제가 서술된다.

N보다 크거나 같은 자연수 중, 조건 $\sim$ 를 만족하는 가장 작은 자연수를 구하여라

예를 들어, BOJ 1040 - 정수 같은 것들이 있다.

Technic 1 - 결정함수를 이용한 자리수 결정

가장 기본이 되는 테크닉은 가장 큰 자리수부터 보면서 현재 보고있는 자리수를 $0 \to 9$ 순서대로 넣어보고 남은 자리수들을 잘 조합했을 때 문제의 조건에 부합시킬 수 있는지를 검사해봐야 한다.

이 때, Leading zero를 피하기 위해 가장 큰 자리수엔 $0$을 넣어주지 않아야 할 것이다.

대개, 남은 자리수를 가지고 문제의 조건에 부합하는 수를 만들 수 있는지 확인하는 그리디한 방법은 현재 자리수를 결정했으면 그 다음수들로는 조건을 충족시키는 수 중 가장 큰 수를 만들어보는 것이다.

예를 들어보자.

$N$보다 큰 수에서 각 자리수 합이 정수 $N$의 각 자리수 합과 같은 수 중, 가장 작은 자연수를 찾아라

$N=1234$라 하면, 각 자리수의 합이 $1+2+3+4=10$ 이 되어야 한다.

제일 첫 자리수를 $1$로 정해보자.

$1???$ 이제 남은 세 자리로 합 $9$를 만들 수 있으면서 가장 큰 수를 찾아보는 것이다.

그건 당연히 $900$이고, 결국 $1900$이란 수를 얻는다.

그런데 $1900>N$ 이므로 가장 첫 자리에 $1$을 넣을 수 있기 때문에 첫 자리수는 $1$로 결정된다.

이제 그 다음 자리로 넘어가보자.

$$ {\color{salmon}1}??? $$

이제 $10??$ 를 시도해볼 수 있는데, 여기서 아무리 수를 크게해봤자 $1090$이고, 이는 $1090<N$ 이기 때문에 첫 자리에 $0$은 불가능함이 보인다.

또한 $1$ 도 마찬가지로 불가능하고, $2$를 넣으려고 시도해보자.

$$ {\color{salmon}1}2?? $$

이제 남은 숫자는 $10-3=7$ 이므로 두 자리 자연수중 자리수 합이 $7$인 가장 큰 수는 $70$이니까, $1270>1234$ 임이 통과되어서 두 번째 자리 수는 $2$로 결정된다.

$$ {\color{salmon} 12 }?? $$

이런 과정을 마지막까지 반복하면, 결국 $1243$ 을 얻어낼 것이다.

문제가 $N$이상이 아닌 $N$이하중 가장 큰 자리수를 찾는 것이라면 $9 \to 0$순으로 순회해주는 것으로 비슷하게 찾을 수 있다.

Technic 2 - 자리수 결정

문제에 따라 정답이 되는 $M$의 자리수가 $N$의 자리수와 일치할 수도, 아닐수도 있다.

BOJ 1040 - 정수 문제를 보면, 정답이 되는 수는 모두 자리수가 달라야 하고 $N$ 이상이여야 하므로 $N=9999$ 같이 나와버리면 $M$은 무조건 5자리수 이상이 된다.

하지만 어떤 문제는 $N$ 자리수와 동일하게 자리수가 고정되는 문제들도 있다.

예를 들어, 숫자들이 모두 달라야 한다는 조건을 제거해보자.

그러나 위 문제처럼 숫자의 자리수가 $N$의 자리수와 항상 일치하지 않는 경우,

대개 이러한 문제의 경우 시간복잡도보단 정확성을 판단하기 때문에 자리수가 고정되있다고 가정하고 탐색 함수를 짜고 그 자리수를 $1$씩 늘려가며 검사를 하는것이 정석적이다.

이런 코드는 이따 연습 문제에서 살펴보자.

Technic 3 - 숫자의 자리수에 대한 정보를 자유롭게 가져올 수 있게 하기

이건 그냥 문제 시작전에 유틸리티 함수들을 몇개 짜고 시작하자는 것이다.

정수의 길이가 몇인지, 앞에서 읽었을 때 $K$ 번째 자리수의 숫자가 어떤 것인지 등이 있다.

int len(ll n) {
   int ret = 0;
   for (; n; n /= 10) ret++;
   return ret;
}

int digit(ll n, int i) {
   return to_string(n)[i] - '0';
}

Technic 4 - 결정함수의 구현 난이도와 상태저장의 공간복잡도 판단하기

앞서 언급했던 예제를 기억하는가?

$$ {\color{salmon} 12 }?? $$

에서 $2$다음 나올 숫자로 $k$가 가능한지 결정하는 것은 어려운 일이나 시간복잡도가 큰 일이 아니였다.

그러나 이 결정 함수를 작성하는 것이 까다로울 때가 있는데, 그런 경우 그냥 진짜 DP를 써서 구현을 한다음에 정답을 역추적하는 방식으로 구현을 할 수 있다.

DP가 담고 있는 값은 $-1(\text{impossible})~or~0,1,\cdots 9$ 으로 이러한 상태에서 정답을 만들어내는 것이 가능한지 불가능한지, 가능하다면 어떤 숫자를 이번 자리에 써야하는지를 저장해둬야 한다.

보통 결정함수 대신 DP를 사용할 땐, 숫자를 문자열로 바꿔준다음 진행하는 것이 구현상 편리하다.

그래서 이러한 유형의 문제를 푸는 방법은 크게 두 가지라고 생각할 수 있다.

1. DP가 아닌 결정함수를 이용해 각 자리수를 직접 결정해가며 정답을 찾아내는 것
2. DP를 이용해 정답이 되는 경로를 찾고, 정답을 역추적하여 도출하는 것

어떤것이 편한지는 문제 by 문제이지만, 대개 1을 먼저 시도해보는 것이 좋을 것 같다.
역추적은 귀찮으니까…

Technic 5 - 이하, 이상의 조건을 미만, 초과로 바꾸기

사실 $N$ 이상의 $\sim$을 구하라를 $N$ 초과로 바꾸는 것은 $N$ 에 대해서만 재빨리 검사해보면 된다.

특정 문제에서 $N$과 같을수도 있음을 자리수를 추적하는 곳까지 들고가버리면 코드 짜기도 복잡해지고 귀찮아지는 경우가 있다.

보통 DP로 풀려는 경우에 그렇다.

따라서 바꿀 수 있다면 바꿔놓고 문제를 해결하도록 하자.

예를 들어, BOJ 1040 - 정수 문제에서 이상을 초과로 바꾸는 방법은 다음과 같다.

int N, K;  
  
void solve() {  
   cin >> N >> K;  
  
   set<int> digit;  
   int M = N;  
   while (M) digit.insert(M % 10), M /= 10;  
   if (sz(digit) == K) {  
      cout << N;  
      return;  
   }
   ...  
}

Technic 6 - 결정 함수의 템플릿 이해하기

문제들마다 결정 함수를 작성해서 풀이를 하겠다고 마음먹었다면, 이 템플릿에서 크게 벗어나는 부분은 없어도 되고, 결정 함수 작성 부분쪽만 문제마다 상이하다는 것을 알고 가자.

vl used(10);
ll N, max_len;

ll tracking(ll prefix, int len) {
   if (len == 0) return prefix;
   for (int d = max_len == len ? 1 : 0; d <= 9; d++) {
      ll tmp = prefix * 10 + d;
      used[d]++;
      // 결정 함수 작성
      // ....
      if (tmp >= N) return tracking(prefix * 10 + d, len - 1);
      used[d]--;
   }
   return -1;
}

void solve() {
   cin >> N;
   for (max_len = len(N);; max_len++) {
      ll ret = tracking(0, max_len);
      if (ret != -1) {
         cout << ret;
         return;
      }
   }
}

위 코드를 살펴보며 대략적인 코드가 어떻게 진행되는지 이해하면 아래 나올 코드들에 대한 이해가 쉽다.

연습 문제 1 - BOJ 1040

BOJ 1040 - 정수

문제를 이제 실제로 풀어보도록 하자.

1. 백트랙킹 풀이

백트랙킹 함수는 다음과 같이 작성하면 된다.

ll tracking(ll prefix, int len) {
   if (len == 0) return prefix;

   for (int d = max_len == len ? 1 : 0; d <= 9; d++) {
      bool valid = true;
      ll tmp = prefix * 10 + d;
      used[d]++;
      // 채울 수 있는 자리수 개수
      int remain_len = len - 1;

      // 현재 만들어진 prefix에서 서로 다른 숫자의 개수
      int k = 0;
      for (int i = 0; i <= 9; i++) if (used[i]) k++;
      if (k > K) valid = false;

      // 아직 사용 안되었지만 사용되어야 하는 숫자의 개수
      int need_fill = K - k;
      if (remain_len < need_fill) valid = false;

      // 새롭게 추가되어야 하는 숫자들은 조건을 만족하면서 가장 커야한다.
      if (need_fill == 0) {
         // 새로운 수를 추가할 필요가 없는 경우
         // 현재 사용된 수중에 가장 큰 숫자만 고른다.
         for (int i = 9; i >= 0; i--) {
            if (used[i]) {
               while (remain_len--) tmp = tmp * 10 + i;
               break;
            }
         }
      } else {
         // 새로운 수를 추가할 필요가 있을 때
         // 일단 9로 많이 채워놓고 나머지 수들을 채운다.
         if (!used[9]) need_fill--;
         while (remain_len > need_fill) {
            tmp = tmp * 10 + 9;
            remain_len--;
         }
         for (int i = 8; i >= 0 && need_fill; i--) {
            if (!used[i]) {
               tmp = tmp * 10 + i;
               need_fill--;
            }
         }
      }

      if (valid && tmp >= N) return tracking(prefix * 10 + d, len - 1);
      used[d]--;
   }

   return -1;
}

일단 현재 각 자리숫자가 쓰였는지 안쓰였는지를 알아야하기 때문에 백트래킹을 하면서 지금까지 $0 \sim 9$의 숫자가 몇번씩 쓰였는지 used배열에 담아둔다.

그런다음 $N=1234, K=2$ 인 경우를 생각해보자.

$$ 1??? $$

부터 시작하자. 필요한 정보를 얻어보자.

채울 수 있는 자리 수: $3$
새롭게 나와야 할 숫자 개수: $1 (K - 1)$

여기서 ??? 를 가장 큰 수로 만드려면, $9$를 많이 채워넣어야한다.

조건을 만족하면서 가장 크게 만들 수 있는 숫자는 $1999$ 이다.

이는 $N$보다 크므로 첫 자리수에 $1$이 들어올 수 있다.​

이제 두 번째 자리를 보자.

$10??$ 과 $11??$ 는 $N$보다 작으므로 넘어간다. ​ $12??$에서 이제 새롭게 나와야할 수가 없으므로 여기서 가장 큰 수를 만드려면

$1222$ 밖에 쓸 수 없다. 이는 $N$보다 작으므로 $2$는 올 수 없다.

$13??$ 를 보자. 여기서 조건에 부합하는 가장 큰 숫자는 $1333$ 이다.

이제 두 번째 자리를 $3$로 고정시키고 $3, 4$ 번째 자리를 보면

$130?$ 는 숫자가 3개 나왔기 때문에 skip

$131?$은 $1313$ 으로 $N$보다 커서 세번째 자리는 $1$이된다.

결국 우리는 $1311$이란 답을 얻을 수 있다.

다른 경우를 보자.

$N$의 자리수 $< K$ 일때는, 사실상 정답은 정해져있다.

N = 4, K = 6 일때를 생각해보자.

정답은 최소 $6$자리인데, $6$자리에서 서로 다른 $6$개의 숫자가 나오는 가장 작은 수는 항 $102345$이다.

비슷하게 $1023 \cdot $ 처럼 답이 정해져있음이 쉽게 보여진다.

in: 1234 8 out: 10234567 in: 1 10 out: 1023456789

이와같이 백트랙킹과 결정함수를 이용하는 경우, 결정함수의 수행속도에 시간복잡도가 영향을 받겠지만,

대략

• $d=$정답의 자리 수​
• $X=$결정함수의 시간복잡도​

일 때, $O(10dX)$ 정도가 될 것이다.

2. DP 풀이

무언가 느꼈는가? 그렇다. 결정 함수가 너무 복잡하다는 것이다.

사실 이런 문제는 비트필드를 이용한 DP로 풀고 역추적을 하는 것이 좀 더 간단할 수도 있다.

DP의 상태를 정의해보자.

$\quad dp[i][state][bigger]$

$i$: 현재 자리 인덱스
$state$: 사용한 숫자의 종류의 bitmask
$bigger$: 이미 $N$보다 커졌는 지에 대한 플래그

저장값: 조건을 만족하는 수를 만드는 것이 불가능하다면 $10$ 같은 더미값, 가능하다면 가능할 때의 최소 자리 숫자$(0 \le x \le 9)$

코드

inline int len(int n) {  
   int ret = 0;  
   while (n) ret++, n /= 10;  
   return max(1ll, ret);  
}  
inline int digit(int n, int i) {  
   string str = to_string(n);  
   if (i >= sz(str)) return -1;  
   return str[i] - '0';  
}  
  
int N, K, LEN, cant = 10;  
  
int dp[20][1 << 10][2];  
  
int fn(int i, int state, int bigger) {  
   int used = __builtin_popcount(state);  
   if (used > K) return cant;  
   if (i == LEN) {  
      if (bigger && used == K) return 1; // dummy value means possible  
      return cant;  
   }  
  
   int &ret = dp[i][state][bigger];  
   if (~ret) return ret;  
  
   for (int d = bigger ? 0 : digit(N, i); d < 10; d++) {  
      if (i == 0 && d == 0)  
         continue; // leading zero  
      int k = fn(i + 1, state | (1 << d), bigger || d > digit(N, i));  
      if (k != cant) {  
         return ret = d;  
      }  
   }  
  
   return ret = cant;  
}  
  
int ans;  
void track(int i, int state, int bigger) {  
   if (i == LEN) return;  
   int nxt = fn(i, state, bigger);  
   ans = ans * 10 + nxt;  
   track(i + 1, state | (1 << nxt), bigger || nxt > digit(N, i));  
}  
  
void solve() {  
   cin >> N >> K;  
  
   set<int> digit;  
   int M = N;  
   while (M) digit.insert(M % 10), M /= 10;  
   if (sz(digit) == K) {  
      cout << N;  
      return;  
   }  
  
   for (LEN = len(N);; LEN++) {  
      memset(dp, -1, sizeof dp);  
      int ret = fn(0, 0, LEN > len(N));  
  
      if (ret != cant) {  
         track(0, 0, LEN > len(N));  
         cout << ans;  
         break;  
      }  
   }  
}

DP에 대해서는 코드가 직관적이기에 주석을 달지 않았다.

어떤 자리수를 볼 때, 이미 커졌는지에 따라 $0$부터 시작할지, 아니면 원래 숫자의 자리부터 시작할지가 중요한 부분이고, 조건을 벗어난 경우엔 cant를 반환해준다.

이 방법의 시간복잡도와 공간복잡도는 결정함수보다 약간 느리겠지만, 문제를 푸는데 지장이 없다.

아래가 결정 함수, 위가 DP를 이용한 풀이이다.

연습 문제들

BOJ 1040 - 정수

CF 1560 - F2

1040 정수의 조건 약화 버전이다. 코포 레이팅은 *2100

CF 915 - C

단순한 결정함수 풀이가 가능하다. 코포 레이팅은 *1700

BOJ 1020 - 디지털 카운터

현재 자리수와 몇개의 획을 쓸 수 있는지를 저장해서 DP로 풀면 풀린다.

BOJ 12890 - 정수 찾기

9를 채우는 결정함수 풀이가 가능하다.

BOJ 1482 - 같은 자리 수

결정함수 풀이가 가능하고, 문제중 가장 까다로웠는데 각각 숫자가 있어야 할 개수를

1 ~ 19 까지 각각 늘려주면서 함수를 호출하면 결정함수 작성이 쉬워진다.