알고리즘 문제 풀이 3
알고리즘 문제 풀이 3
최근에 푼 재미있는 문제들을 포스팅 해보겠습니다.
BOJ 1066번 에이한수
각 자리수를 등차 수열을 이루는 연속한 수들끼리 묶어서 $A$ 개의 그룹으로 나눌 수 있으면 $A$-한수 라고 할때, $A$-한수 이고 $(A - 1)$-한수가 아니면서 각 자리수가 비내림차순인 $N$ 자리 자연수의 개수를 구하는 문제입니다.
다음과 같은 사실을 관찰해 봅시다.
$A$-한 수 이고 $A < N$ 이면 $(A + 1)$-한 수이기도 하다.
위와 같은 사실이 성립하는 이유는 $A < N$ 이기 때문에 적어도 한 그룹에는 2개 이상의 연속된 수가 포함되어 있고, 이를 임의로 두 그룹으로 나눠주어도 각 그룹이 등차 수열을 이룬다는 조건을 만족시키기 때문입니다.
따라서, $A$-한수 이면서 $(A - 1)$-한수가 아니라는 것은 이 자연수를 등차 수열을 이루는 연속한 수들끼리 묶어서 그룹으로 나눌 때, 그룹의 개수의 최솟값이 $A$라는 의미입니다.
그렇다면 자연수가 주어지면 그 자연수의 자리수를 연속한 수들끼리 묶어서 그룹으로 나눌 때, 그룹의 개수의 최솟값은 어떤 방법으로 구할 수 있을지를 고민해봅시다.
이는 greedy한 방법으로 구할 수 있습니다. 자연수를 맨 앞(가장 높은 자리수)에서 부터 시작하여 등차 수열을 이룰 때까지 최대한 길게 확장하여 한 그룹으로 묶고, 그 다음 자리부터 시작하여 마찬가지의 process 를 반복하면, 가장 적은 수의 그룹으로 자연수를 나눌 수 있습니다.
위의 greedy한 방법이 성립하는 이유는 다음과 같습니다. 만약 맨 앞에서 부터 시작해서 어떤 자리수까지 조건을 만족시키며 그룹을 확장시킬 수 있는 상황이지만 확장시키지 않은 최적해가 있다고 가정해 봅시다. 그렇다면 우리는 그 최적해의 두번째 그룹의 첫번째 수를 때어다가 첫번째 그룹으로 붙여주면, 조건을 위배시키지 않고 그룹의 개수는 최적해보다 작거나 같으면서 맨 앞 그룹의 개수가 더 많은 해를 얻을 수 있습니다. 이를 반복해서 적용하면, 맨 앞 그룹의 개수가 최대한 많은 최적해가 존재함을 보일 수 있고, 맨 앞 그룹을 고정하면 남은 문제는 동일한 문제이므로 같은 방법을 반복 적용하면 전체 문제의 최적해를 얻을 수 있음을 보장할 수 있습니다. 따라서 위의 greedy한 방법이 성립한다는 것을 알 수 있습니다.
이 greedy한 방법을 dynamic programming에 적용시켜서 본 문제를 해결할 수 있습니다.
우선 $A$의 값의 범위를 제한하여 보다 tight하게 dynamic programming 을 적용합시다.
$A > 9$ 이면 본 문제의 답은 $0$이다.
문제에 각 자리수가 단조 증가하는 자연수만을 원한다고 하였으므로, 자연수를 단순히 1의 그룹, 2의 그룹, …, 9의 그룹으로 나누어도 많아야 9개의 그룹이 나오므로 실제 이 자연수를 최소 개수의 그룹으로 나누면 9개 이하의 개수로 나눌 수 있음을 알 수 있습니다. 따라서 $A > 9$인 수가 있어서 우리가 원하는 자연수를 분할하는 최소 그룹수가 될 수 없습니다. 그러면 이제 dynamic programming 을 정의하여 보겠습니다.
dp(x, la, d, a) : 지금 x번째 자리수를 볼 차례이고, 이전 수가 la 였고, 이전 수가 속한 그룹의 등차가 d였고, 이전 그룹의 개수를 포함해서 a개의 그룹을 더 만들어야할 때 x번째 이후의 자리수들을 적절히 결정하는 경우의 수
이렇게 dp 를 정의하면, x번째 자리에 $0$ 부터 $9$까지 집어넣는 각각의 경우에 대해서 모두 transition 을 해 줄 수 있으므로 dp table을 모두 채울 수 있습니다.
본 문제의 답은 $dp(1, 1, -1, A) + dp(1, 2, -1, A) + dp(1, 3, -1, A) + … + dp(1, 9, -1, A)$ 와 같은 식으로 구할 수 있습니다.
시간 복잡도는 $O(N * 10^4)$ 입니다.
아래는 이 문제를 해결하는 c++ 코드입니다.
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int N, A;
int cc[1010][11][11][11];
int dp(int x, int la, int d, int a) {
if(x == N) return a == 0;
int &ret = cc[x][la][d][a];
if(ret != -1) return ret;
ret = 0;
if(d != 10) {
for(int i = la; i <= 9; i++) {
if(i == la + d) {
ret += dp(x + 1, la + d, d, a);
ret %= mod;
}
else if(a) {
ret += dp(x + 1, i, 10, a - 1);
ret %= mod;
}
}
}
else {
for(int i = la; i <= 9; i++) {
ret += dp(x + 1, i, i - la, a);
ret %= mod;
}
}
return ret;
}
int main() {
cin >> N >> A;
if(9 < A) {
cout << 0;
return 0;
}
memset(cc, -1, sizeof(cc));
int ans = 0;
for(int i = 1; i <= 9; i++) {
ans += dp(1, i, 10, A - 1);
ans %= mod;
}
cout << ans;
}
BOJ 16990번 마법 장벽
2차원 평면에 지나갈 수 없는 점(마법 장벽)이 pattern 을 이루며 무한히 있을 때, 특정 직선(포탄)이 지나갈 수 없는 점에 부H히는지 아닌지를 판별하는 문제입니다.
첫번째로 주목해야 할 점은 pattern 의 주기가 매우 짧다는 것입니다. ($L_i \leq 6$) 이를 활용하여서 문제를 풀어봅시다.
chk(i, j, k) 라는 $666$ 배열에 i 로 나눈 나머지가 j 인 기울기를 가지는 포탄의 초기 발사 위치가 i로 나눈 나머지가 k 일때 이 포탄이 중간에 막히는가를 check 해 두기로 합시다.
우선 chk 배열은 0으로 초기화 해둡니다.
그런 다음 마법 장벽의 길이 len과 pattern 이 들어올 때마다 모든 j, k 값에 대해 chk(len, j, k) 값을 1로 바꿔줄지 말지를 결정할 수 있습니다. 따라서 마법 장벽 입력을 모두 받고 나면 chk(i, j, k) 에 올바른 값이 저장되어 있을 것입니다.
이제 포탄을 입력으로 받으면 그 포탄의 기울기와 초기 위치를 $i(1 \leq i \leq 6)$로 나눈 나머지를 $d_i, p_i$ 라고 할 때, $chk(i, d_i, p_i)$ 가 전부 1이 아니라면(막혀 있지 않다면) 통과되는 포탄으로 판단할 수 있습니다.
시간 복잡도는 $O(N * maxlen^2 + M * maxlen)$ 입니다.
아래는 위와 같은 방법으로 문제를 해결하는 c++ 코드입니다.
#include<bits/stdc++.h>
using namespace std;
const int MN = 10010;
int N, M;
string S[MN];
int chk[7][7][7];
int main() {
std::ios::sync_with_stdio(false);
cin >> N >> M;
for(int i = 0; i < N; i++) {
int len; cin >> len >> S[i];
for(int j = 0; j < len; j++) {
for(int k = 0; k < len; k++) {
chk[len][j][k] |= S[i][ (j * (i + 1) + k) % len ] == '0';
}
}
}
int ans = 0;
for(int i = 0; i < M; i++) {
int p, d; cin >> p >> d;
bool ok = false;
for(int j = 1; j <= 6; j++) {
if(chk[j][ (d % j + j) % j ][ (p % j + j) % j ]) {
ok = true;
break;
}
}
if(!ok) ans++;
}
cout << ans;
}