[종만북] 문제: ZIMBABWE
문제
최대 15자리 정수 $e$와 정수 $k(2 \leq k \leq 20)$가 주어졌을때, $e$의 각 자리를 바꾼 $e’$의 개수를 세는 문제입니다.
$e’$는 다음과 같은 조건이 있습니다.
- $e’ < e$
- $e’ \mod k = 0$
서론
이번에는 입력이 순열인 경우에 대해서 Dynamic programming을 적용해보려고 합니다.
알고리즘 구상
값이 중복돼요
이 문제는 결국 $e’$의 후보를 만들어야 합니다. 후보를 어떻게 만들까요? 방법은 크게 2가지가 있습니다.
- $e$를 오름차순으로 정렬한 $digit$를 오름차순으로 탐색하면서 어떤 자릿수가 조건이 성립되지 않으면, 그 문자는 연속된 중복문자이므로 다시 뽑지 않습니다.
- 각 숫자 개수의 frequency Table을 만들어서 재귀 트리 경로를 만듭니다.
2번 방법은 함수 구현이 쉽지만, Dynamic Programming을 적용하기 매우 어렵습니다.
frequency Table을 bitmask 기법을 이용해 저장한다고 해봐도, $e$는 15자리 수이므로 각 자릿수를 표현하기 위해서는 최소 4 bit, 총 40 bit가 필요합니다. 이는 int의 범위를 넘어섭니다. 따라서 1번 방법을 써야합니다.
1번 방법(교과서 제시 방법)
- $e$를 오름차순으로 정렬한
string$digit$을 만듭니다. (편의상string으로 하겠습니다.) - $digit$의 어떤 자릿수를 사용할 때, 조건을 하나라도 만족하는지 검사합니다.
- 조건은 이렇습니다. 조건을 만족하지 않으면 통과해서 중복 값을 피할 수 있습니다.
- 앞자리가 없습니다.
i = 0 - 앞자리와 어떤 자릿수의 값이 다릅니다.
digit[i-1] != digit[i] - 앞자리를 사용했습니다.
taken[i-1] = true
- 앞자리가 없습니다.
1번 방법은 bool배열을 이용해 풀면 됩니다. bool[15]는 bitmask기법을 통해 int형으로 표현할 수 있습니다.
알고리즘에서는 함수의 파라미터 taken를 통해 구현합니다.
따라서 Dynamic Programming를 적용하기 쉽습니다.
조건 1 검사하기
$e’$가 조건 1에 만족하는지 확인하는건 쉽습니다. $e’$와 $e$의 자릿수는 같습니다. 가장 큰 자릿수부터 비교해보죠!
- $e’[i] < e[i]$ 무조건 조건 1을 만족합니다.
- $e’[i] = e[i]$ 다음 자릿수가 존재한다면 다음 자릿수를 비교합니다.
- $e’[i] > e[i]$ 무조건 조건 1을 불만족합니다.
알고리즘에서는 조건 1에 부합하는지를 함수의 파라미터 less를 통해 구현합니다.
조건 2 검사하기
이제 $e’$가 조건 2에 만족하는지 봐야합니다.
그냥 무식하게 15자리 $e’$를 어딘가 저장했다가 이를 모듈러 연산을 한다고 가정해봅시다. 복잡하죠, 모듈러 연산의 성질을 이용해서 연산 부하를 줄여보고자 합니다.
$(a + b) \mod m = \big((a \mod m) + (b \mod m)\big) \mod m$
예시를 들어봅시다.
$119 \mod 7 = 0$
$100 \mod 7 = 2, 10 \mod 7 = 3, 9 \mod 7 = 2, 2 + 3 + 2 \mod 7 = 0$
이렇게 각 자리를 따로 계산해서, 남은 값mod을 넘겨주기만 하면 됩니다!
알고리즘에서는 모듈러 연산값 저장을 함수의 파라미터 mod를 통해 구현합니다.
알고리즘 순서
- $e$를 $digit$으로 변환합니다.
- $digit$을 이용해서 $e’$후보를 만듭니다.
- $e’$에 대해 각 자리마다 조건 1과 조건 2가 만족하는지 검사합니다.
생각보다 단순하지 않나요?
알고리즘 구현
재귀함수
교과서 내용이 정석이여서 교과서 내용을 가져왔습니다. taken에 적용된 bitmask기법과, mod의 성질, less까지 잘 어우러져 있는 DP함수입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int DP[1 << 14][20][2];
int count(int index, int taken, int mod, int less) {
if (index == e.size()) return (less && mod == 0) ? 1 : 0;
int &ret = DP[taken][mod][less];
if (ret != -1) return ret;
ret = 0;
for (int next = 0; next < e.size(); next++) {
if (taken & (1 << next)) continue;
if (!less && e[index] < digit[next]) continue;
if (next && digit[next - 1] == digit[next] &&
(taken & (1 << (next - 1))) == 0)
continue;
int nextTaken = taken | (1 << next);
int nextMod = (mod * 10 + digit[next] - '0') % m;
int nextLess = less || e[index] > digit[next];
ret += count(index + 1, nextTaken, nextMod, nextLess);
ret %= 1000000007;
}
return ret;
}
modulo 연산
1
int nextMod = (mod * 10 + digit[next] - '0') % m;
이 코드는 재귀를 이용해 모듈러 연산을 구현한 것이나 다름 없습니다.
최종 코드
여기에서 확인하세요!
알고리즘 개선방안
만약 모듈러 연산을 더 응용한다면?
사실 이 알고리즘 문제는 e’가 m의 배수인지 물어보는 문제에 가깝습니다.
만약 m이 2라면? 끝에 아무 짝수나 넣기만 하면, 나머지 부분에 대해서 조건 1만 만족하면 되겠죠.
1
if (index == e.size()) return (less && mod == 0) ? 1 : 0;
에서
1
if (index == e.size()) return 1;
이런식으로 줄일 수 있겠죠..! 아마 2가 아닌 다른 수에도 법칙이 존재할 것입니다.
아마 구현한다면, switch-case문을 추가하면서 2부터 20까지 경우의 수를 전부 생각해야 하겠죠.
상상으로만 남기겠습니다!