[BOJ 19533] [UCPC 2020 예선] 길이 문자열
오늘은 (제 기준) 초고난도 문제를 들고 왔습니다. 너무 어려웠어요. 물론 시간 안에 못 풀었습니다. 헤헤
원래는 이 포스팅을 쓰지 않았겠지만 제가 삽질한 시간이 너무도 아깝기 때문에 쓰는 것입니다.
시작해보겠습니다.
https://www.acmicpc.net/problem/19533
19533번: 길이 문자열
각 테스트 케이스마다 길이 $a\times 10^b$인 길이 문자열을 출력한다. 이때 $a\times 10^b \geq 21$이면 문자열의 맨 앞의 $17$글자만 출력 예시와 같은 형식으로 출력한다.
www.acmicpc.net
기본적으로 길이 문자열은 십진법 숫자들이 -로 구분되어있는 문자열이고 십진법 숫자의 앞에 0을 넣는 것은 불가능합니다. 이 문자열의 특징은 각 숫자에서 - 전까지 끊었을 때 그 숫자의 값이 문자열의 총길이라는 것입니다.
이제 생각을 해보면 어떤 길이의 길이 문자열이 있다면 해당 문자열의 맨 끝에 그 숫자가 써져있을 것입니다. 그래서 그 문자열의 뒷부분 숫자와 - 까지 알고 있는 상태입니다.
(예시)
길이 1234인 길이 문자열
.....-????-????-????-1234
문자열의 끝은 반드시 "-1234"이다.
그렇다면 끝의 -와 숫자를 빼면 또다시 길이 문자열이 될 것입니다. 그리고 여기서 중요한 것은 해당 문자열의 길이를 알고 있습니다. 방금 배제한 -와 숫자의 값을 알고 있으므로 이 부분의 길이를 알 수 있기 때문입니다.
(예시)
길이 1234인 길이 문자열
.....-????-????-????-1234
"-1234"를 삭제하면 1234 - 1 - 4 = 1229의 길이를 가지는 길이 문자열이 된다.
해당 문자열은 다시 다음과 같은 모양을 띠는 것을 알 수 있다.
.....-????-????-1229
이렇게 생각하면 귀납법을 통해 길이가 주어졌을 때 해당 길이 문자열이 존재하고 유일함을 알 수 있습니다.
(정리) 임의의 자연수 N에 대해 길이 N의 길이 문자열이 존재하고 이는 유일하다.
좋습니다. 이제 위와 같이 생각해보면, 문제에서 답은 길이 문자열의 앞부분 일부만 요구하므로, 길이 N과 길이 N - 1 - (숫자 N의 길이)은 동등한 관계임을 알 수 있습니다. 그렇다면 (숫자 N의 길이)가 변하지 않는 한 같은 숫자를 계속 빼는 꼴이므로 해당 길이가 변하지 않는 범위 내에서는 나머지 연산을 통해 빠르게 동등관계이면서 작은 길이를 알아낼 수 있습니다.
(예시)
길이 1234인 길이 문자열
- 5의 길이만큼 반복적으로 뺄셈
- 1234 - 1000 = 234의 범위 내에서 길이는 4로 유지
=> 234 % 5 = 4를 남긴 1004와 동등
나머지 연산을 통해 동등관계를 계산할 때 숫자의 자릿수를 하나씩 줄일 수 있으므로 지수 수준의 빠른 연산이 가능합니다. 하지만 문제에서 요구하는 복잡도에서는 아직 부족합니다.
여기서 우리는 이렇게 나머지 연산을 통해 숫자를 계속 줄일 때, 그 결과가 10^n에 매우 근접한 범위에서 나오는 것을 알 수 있습니다. 따라서 이 부분을 메모해놓고 한 번만 나머지 연산을 한 후에 그 결과를 바로 가져다 쓰면 되겠습니다.
여기서부터는 저도 UCPC 2020 주최 측의 해설을 참고하였습니다.
일단 위에서의 내용을 토대로 생각해보면 같은 길이를 가지는 범위 내에서는 같은 값을 빼면서 동등관계를 계산할 수 있으므로 해당 값만큼의 주기를 가진다고 볼 수 있습니다. 따라서 주기 내에서만 알고 있으면 되겠습니다.
주기는 1 + (해당 구간의 숫자의 길이)가 되겠습니다. 이를 토대로 (10^n - 1 - n) ~ (10^n) 구간을 저장해서 계산하면 되겠습니다. 이때 주기보다 1개 더 많은 숫자를 계산하였습니다. 이는 10^n으로 넘어가면서 주기가 1만큼 길어지고 이 숫자가 추가되기 때문입니다.
10^n 길이 문자열과 10^n - 1 길이 문자열은 끝을 제외하고 동등합니다. 자릿수가 1 커지면서 숫자의 차이를 흡수해버리기 때문입니다.
(예시)
999 길이 문자열
...-???-996-999
1000 길이 문자열
...-???-996-1000
따라서 10^(n-1) ~ (10^n - 1) 구간의 주기에 (10^n - 1)의 답이 (10^n)의 답으로 복사되는 모습을 볼 수 있습니다.
(예시)
996의 답: 1-3-5-7-9-12-15-1...
997의 답: 1-3-5-7-10-13-16-...
998의 답: -2-4-6-8-11-14-17...
999의 답: 1-3-5-7-9-12-15-1...
1000의 답: 1-3-5-7-9-12-15-1...
999의 답과 1000의 답이 똑같음을 볼 수 있다.
또한 여기서 관찰할 수 있는 것은 같은 답을 가지는 숫자들을 하나의 그룹으로 묶었을 때 각 그룹의 숫자들이 연속되어 나옴을 볼 수 있습니다. 즉 16이 나타나는 997이 하나, 17이 나타나는 998이 하나, 그리고 15가 나타나는 숫자는 999, 1000, 996으로 주기를 가지는 점을 고려했을 때 연속되어 나온다는 점을 알 수 있습니다. 또한, 자릿수가 늘어날 때마다 주기가 늘어나는데, 이때 추가되는 숫자는 항상 이웃하는 숫자와 같은 숫자임을 알 수 있습니다. 결국, 자릿수가 계속 늘어나더라도 주기 내에서 같은 답을 가지는 그룹은 연속되어 나타납니다. 이 점을 활용하여 연속된 숫자의 시작 부분만 저장해놓으면 되겠습니다.
이제 코드를 보겠습니다.
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct{
int mantissa;
int exponent;
} bignum_t;
// length of decimal number
int declen(int N){
int len = 0;
while(N != 0){
N /= 10;
len++;
}
return len;
}
// length of decimal number wrapper for bignum_t
int declenbig(bignum_t bN){
return declen(bN.mantissa) + bN.exponent;
}
// calculate 10**power
int power10(int power){
int res = 1;
for(int k=0;k<power;++k)
res *= 10;
return res;
}
// calculate bN % d for bignum_t type bN
int remainderbig(bignum_t bN, int d){
long long rem = bN.mantissa % d;
int exponent = bN.exponent;
long long base = 10 % d;
int res;
if(exponent == 0) res = (rem % d);
else{
while(exponent > 1){
if(exponent % 2 != 0){
rem = (rem * base) % d;
exponent--;
}
base = (base * base) % d;
exponent /= 2;
}
res = ((rem * base) % d);
}
return res;
}
class lenstring{
private:
enum{
PATTERN_17 = 0,
PATTERN_18 = 1,
PATTERN_19 = 2,
} pattern_const_t;
typedef struct{
// 0: -2-4-6-8-11-14-17
// 1: 1-3-5-7-9-12-15-18
// 2: 1-3-5-7-10-13-16-19
int start[3];
} pattern_t;
vector<pattern_t> pattern;
int querycase(int power, int rem){
int r = power+2, pat = -1;
for(int k=0;k<3;++k){
if(r > pattern[power].start[k] && pattern[power].start[k] >= rem){
r = pattern[power].start[k];
pat = k;
}
}
if(pat == -1){
for(int k=0;k<3;++k){
if(r > pattern[power].start[k]){
r = pattern[power].start[k];
pat = k;
}
}
}
int reduceval;
switch(pat){
case PATTERN_17: reduceval = 23; break;
case PATTERN_18: reduceval = 21; break;
case PATTERN_19: reduceval = 22; break;
default: reduceval = -1; break;
}
return reduceval;
}
void printlenstring(int val){
if(val>=21){
val -= (((val - 21) / 3) * 3);
switch(val){
case 23:
printf("-2-4-6-8-11-14-17...\n");break;
case 21:
printf("1-3-5-7-9-12-15-1...\n");break;
case 22:
printf("1-3-5-7-10-13-16-...\n");break;
default:
printf("calculation error\n");break;
}
} else{
vector<int> viewvals;
viewvals.reserve(8);
while(val>1){
viewvals.push_back(val);
val -= (1 + (val>=10 ? 2 : 1));
}
if(val == 1) putchar('1');
for(int k=viewvals.size()-1;k>=0;--k)
printf("-%d", viewvals[k]);
putchar('\n');
}
}
public:
lenstring(){
//fix parameter using constraint
const int N = 1e6+12;
//calculate pattern
/*
pattern[k]
10^k - (this value) ~ 10^k - (any other smallest value)
*/
pattern.resize(N);
pattern[2] = {{2, 1, 3}};
for(int k=3;k<=N;++k){
bignum_t bN;
bN.mantissa = 9;
bN.exponent = k-1;
int shift = remainderbig(bN, k+1) - 1;
for(int l=0;l<3;++l){
pattern[k].start[l] = ((pattern[k-1].start[l] + shift) % (k+1)) + 1; // 1 ~ (k+1)
}
}
}
int viewhead(bignum_t bN){
int reduceval; // must be dec of length 2 or smaller
int totallen = declenbig(bN);
if(totallen <= 2){
reduceval = bN.mantissa * power10(bN.exponent);
} else{
bignum_t difference = bN;
difference.mantissa -= power10(totallen-1 - bN.exponent);
int rem = (totallen+1 - remainderbig(difference, totallen+1)) % (totallen+1);
// 1 * 10^(totallen-1) - rem
reduceval = querycase(totallen-1, rem);
}
printlenstring(reduceval);
return reduceval;
}
};
int main() {
int T;
scanf("%d",&T);
lenstring P;
for(int k=0;k<T;++k){
bignum_t bN;
scanf("%d%d", &bN.mantissa, &bN.exponent);
P.viewhead(bN);
}
}
lenstring 클래스의 생성자에서 (10^n - 1 - n) ~ (10^n) 구간의 정보를 문제의 조건 내에서 전부 계산해놓습니다.
viewhead 함수가 가장 큰 그림을 담고 있는 함수입니다. 숫자가 작은 경우는 그냥 int로 변환하여 계산해주면 되겠습니다. 이때 구분을 위해 숫자의 총길이 totallen을 이용하였습니다. 해당 숫자의 자릿수를 유지하면서 가장 작은 숫자와의 차이 값을 이용해 나머지 연산 remainderbig을 통해 10^n에 근접한 숫자로 바꿔줍니다. 그 값을 이용해 querycase 함수를 통해 바로 답으로 변환해줍니다.
그 이후 그 값을 printlenstring을 통해 출력해줍니다.
이번 문제는 정말 심리적으로도 좀 압박이 될 만큼 어려웠습니다. 그리고 이 문제를 통해 알고리즘 최적화의 방법을 또 하나 제대로 배운 것 같습니다. 삽질을 한 부분은 여러 부분인데, 굉장히 찾기 어려웠던 부분이 remainderbig의 버그였습니다. int 숫자를 곱셈하는 과정에서 오버플로우가 발생해서 입력된 숫자의 지수가 굉장히 커졌을 때 버그가 있었습니다. 숫자의 지수가 커졌을 때는 정확한 답을 알아내는 것이 굉장히 어렵기 때문에 난이도가 더 높았던 것 같습니다.
감사합니다.