보통 이런 문제는 실제 n번째 문자열을 직접 구성해서 거기서 k번째를 가져오도록 못하게 메모리 또는 시간제한을 둡니다. 즉, 문제를 접근했을 때 직관적으로 떠오르는 풀이는 틀리게 문제를 구성한다는 거죠. 따라서 문자열을 빌드업하며 계산하는 방식은 사용할 수 없습니다.
문제)
베이스 : = "abc"
점화식 : = "fx"++"."+
1. n번째 문자열()의 길이를 먼저 예측해보자!
따라서 똑똑하게 k번째 문자열을 찾아갈 수 있어야 합니다. 점화식에 등장하는 구조를 보면 이전 상태를 이용하는 것을 관찰해봅시다. n번째 문자열()의 길이를 L[n]이라고 하면 L[n]은 점화식을 통해 구할 수 있습니다.
L[n] = (n번째 이전의 문자열 길이의 합) + 기존 구성 문자열 길이
문제의 경우 길이 점화식은 아래와 같습니다.
L[n] = 2*L[n-1] + 3
문자열 자체의 점화식을 도출해낼 수 있다면 당연히 그 길이에 대한 점화식도 구할 수 있습니다.
2. 구간을 나눠서, k번째가 어디 구간에 속하는지 확인하자!
길이 점화식을 다시금 정리해봅시다. 순서대로 나열해보면
L[n] = 2 + L[n-1] + 1 + L[n-1]이 됩니다.
그럼 여기서 k번째를 찾는다고 하면 앞에서부터 탐색해 나가면 됩니다. k번째가 2번째 이하라면 "fx"에 속할테고, 2번째 초과 && 2 + L[n-1]번째 이하라면 L[n-1]번째 문자열에 속한 문자가 됩니다. 이때 에서 k번째를 다시 예측하는 구조를 가지게 되죠. 이런 방식을 찾을 때까지 적용시켜 나갑니다.
슈도 코드는 다음과 같습니다.
function find(n, k)
if n = 0
return S0[k]
if k <= 2
return "fx"[k]
else if k <= 2 + L[n-1]
return find(n-1, k-2) //Sn-1에 대해 다시 예측
else if k <= 2 + L[n-1] + 1
return '.'
else
return find(n-1,k-2-L[n-1]-1) //Sn-1에 대해 다시 예측
핵심은 k번째 구간이 '어디에 속하는 지를 확인하여 현재 어느 위치에 있을지 예측'하는 것이죠.
위의 문제의 경우 4개의 구간이 있으면 1번째 구간은 "fx", 2번째는 , 3번째는 ".", 4번째는 으로 구간을 나눌 수 있습니다. 따라서 구간별로 길이가 "정해져 있음"에 우리는 k번째가 쉽게 어느 구간에 있을지 계산 가능하죠.
* 첨언
위의 방식은 꼬리 재귀(tail recursion)이기 때문에 대부분 반복문으로 대체 가능합니다. 구현은 재귀로 해도 좋고, 반복문으로 순차 접근해도 좋습니다. 단, 재귀는 스택 메모리를 잡아먹기 때문에 n의 범위가 크면 클수록(하위 문자열에 대해 다시 예측하는 모델이기에) 그만큼 메모리를 가진다는 것을 알아두세요.
="What are you doing at the end of the world? Are you busy? Will you save us?".
="What are you doing while sending ""? Are you busy? Will you send ""?"
에서 을 감싸는 큰따옴표(")가 있음을 주의합시다.
마찬가지로 똑같은 방식을 취하면 매우 쉽게 점화식을 구할 수 있습니다.
길이 L에 대해 정리해봅시다. 하는김에 분할마저 한다면 아래와 같습니다.
L[n] = strlen("What are you doing while sending \"")
+ L[n-1]
+ strlen("\"? Are you busy? Will you send \"")
+ L[n-1]
+ strlen("\"?")
이젠 구간만 나누면 되는데.. 이게 웬.. n제한이 10만? L[n]이 2의 승수로 증가하기 때문에 2의 10만 승수는 표현할 수가 없습니다. 사실 이게 이 문제의 출제 의도이기도 하겠죠.
생각을 다시해보면 그럴 필요가 없다는 걸 깨닫게 됩니다.
k 제한을 보면 10의 18승수까지만 확인하고 싶어하는 걸 볼 수 있습니다. C++ 기준 long long으로 표현할 수 있는 범위가 약 9*10의 18승수이므로 충분히 표현이 가능한 것이지요. 또 문자열 범위를 벗어나는 위치에 대해서는 마침표(.)를 출력하라고 했으니 그부분도 신경써서 코드 짜주시면 되겠습니다. +) 첨언을 하자면 n=55일 때 L[55] = 약 5*10의 18승수로 k 범위를 포괄합니다. k에 있는 위치 문자를 정확히 출력하기 위해서는 포함되는 구간을 모두 예측할 수 있어야하기 때문에 n=55까지 L 배열을 구할 필요가 있습니다.
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
using ll = long long;
const int MAX_N = 56;
const char* f0 = "What are you doing at the end of the world? Are you busy? Will you save us?";
const char* f1[] = { "What are you doing while sending \"", "\"? Are you busy? Will you send \"", "\"?" };
int f0L, f1L[3];
ll L[MAX_N];
int main() {
char ans;
int q, n, i, f1Ls = 0;
ll k;
f0L = strlen(f0);
for (i = 0; i < 3; i++) {
f1L[i] = strlen(f1[i]);
f1Ls += f1L[i];
}
L[0] = f0L;
for (i = 1; i < MAX_N; i++) L[i] = 2 * L[i - 1] + f1Ls;
scanf("%d", &q);
while (q--) {
scanf("%d%lld", &n, &k);
k -= 1;
ans = 0;
while (!ans) {
if (!n) ans = k < f0L ? f0[k] : '.';
else {
if (k < f1L[0]) ans = f1[0][k];
else if (n <= MAX_N) {
k -= f1L[0];
if (k < L[n - 1]) n -= 1;
else {
k -= L[n - 1];
if (k < f1L[1]) ans = f1[1][k];
else {
k -= f1L[1];
if (k < L[n - 1]) n -= 1;
else {
k -= L[n - 1];
ans = k < f1L[2] ? f1[2][k] : '.';
}
}
}
}
else {
k -= f1L[0];
n -= 1;
}
}
}
printf("%c", ans);
}
return 0;
}
드래곤 커브 문제처럼 규칙성을 파악해봅시다. 연산이고 뭐고 이런 유형의 문제는 K가 굉장히 크다면 당연히 규칙성이 있어야만 합니다.
= a, = c라고 합시다.
은 정가운데에 있는 문자가 'a'인 군을 뜻하고, 은 정가운데에 있는 문자가 'c'인 군을 뜻하는 걸로 정의해봅시다.
수열 규칙을 보는게 힘드니 차례로 써봅시다.
a
c
a
= a
c
= c
a
= a
c
= c
가운데 문자가 'a'인 군은 , 'c'인 군은 의 문자열을 가지게 됩니다.
(놀랍게도 이 문제는 드래곤 커브와 똑같은 점화식, 풀이을 가지게 됩니다.)
이제 길이 L에 대해서 생각해봅시다.
의 길이 La[i]와 의 길이 Lb[i]는 아래처럼 정의됩니다.
문제에서 정의하길, N=10^2017으로 고정했으므로 10^2017번째 문자열은 어떻게 생겨먹었을까요? K 범위를 보고 힌트를 얻을 수 있습니다. K가 고작 10^18밖에 되지 않기 때문에 10^18을 넘는 문자열을 구할 필요가 없습니다. 문자열 점화식이 "현재문자열=이전문자열+문자+이전문자열" 이기 때문이죠.
이제 구간으로 분할해 봅시다.
La[n] = La[n-1] + 1 + Lb[n-1]
Lb[n] = La[n-1] + 1 + Lb[n-1]
둘 다 구간이 같기 때문에 하나의 함수에 담을 수 있습니다!
#include<cstdio>
const int LIMIT = 65;
using ll = unsigned long long;
ll L[LIMIT] = { 1 };
char find(int n, ll k, int f) {
if (n == 0) return f ? 'a' : 'c';
if (k < L[n - 1]) return find(n - 1, k, 1);
else if (k == L[n - 1]) return f ? 'a' : 'c';
else return find(n - 1, k - L[n - 1] - 1, 0);
}
int main() {
int T, i;
ll K;
for (i = 1; i<LIMIT; i++) L[i] = 2 * L[i - 1] + 1;
scanf("%d", &T);
while (T--) {
scanf("%lld", &K);
printf("%c\n", find(63, K - 1, 1));
}
return 0;
}
+) Googol String 문제는 완전 똑같아서 따로 해설하진 않겠습니다..
#include<cstdio>
const int LIMIT = 65;
using ll = unsigned long long;
ll L[LIMIT] = { 1 };
int find(int n, ll k, int f) {
if (n == 0) return !f;
if (k < L[n - 1]) return find(n - 1, k, 1);
else if (k == L[n - 1]) return !f;
else return find(n - 1, k - L[n - 1] - 1, 0);
}
int main() {
int tc = 1, T, i;
ll K;
for (i = 1; i<LIMIT; i++) L[i] = 2 * L[i - 1] + 1;
scanf("%d", &T);
while (T--) {
scanf("%lld", &K);
printf("Case #%d: %c\n",tc++, find(63, K - 1, 1) + '0');
}
return 0;
}
여기서 중요한 관찰포인트는 바로 모든 문자가 제자리로 돌아올 수 있다는 점입니다. 먼저 X부터 생각해보죠
X는 YZ가 되고 YZ는 ZX가 되죠.
그런데 말입니다. 그 다음 문자는 어떻게 되죠?
바로 처음에 시작했던 X와 두 번째 문자열 YZ가 복원이 됐습니다! 우연일까요 ? 다음 문자열은
일반화 시켜본다면 N단계의 문자열=(N-3단계 문자열)(N-2단계 문자열)로 볼 수 있습니다.
이는 써보면서 눈에 들어올 수 있으나 굳이 증명하자면, X가 Y만을 생성한다고 한다면 X->Y->Z->X의 순환 구조로 세 번만에 제자리(다시 X로 돌아옴)로 돌아올 수 있습니다. 하지만 X는 YZ를 생산하므로 X의 다음 단계 Y와 그 다음 단계 Z를 동시에 생성하기 때문에 세 번만에 제자리로 돌아오는 문자열과 두 번만에 제자리로 돌아오는 문자열로 생성되기 때문에 증명이 가능합니다.
자 이제 길이에 대해서 정리해봅시다.
의 길이 L[n] = L[n-3] + L[n-2] (n >= 4), L[1] = 1, L[2] = L[3] = 2
구간이 딱 두 개밖에 없으니, 다른 문제보다 간단해집니다. n(n>=4) 단계의 문자열은 모두 1~3 단계 문자열로 만들 수 있습니다. 기저 사례를 이 셋으로 두고 탐색을 진행하시면 되겠습니다~
#include<cstdio>
using ll = unsigned long long;
const int MAX_N = 100;
const char* base[3] = { "X", "YZ", "ZX" };
ll dpLength[MAX_N] = { 1,2,2 }, dpCnt[MAX_N][3] = { {1,0,0},{0,1,1},{1,0,1} };
ll getLength(int p) {
ll& ret = dpLength[p];
if (ret) return ret;
ret = getLength(p - 3) + getLength(p - 2);
for (int i = 0; i < 3; i++)
dpCnt[p][i] = dpCnt[p - 3][i] + dpCnt[p - 2][i];
return ret;
}
char find(int n, ll k) {
if (n < 3) return base[n][k];
if (k < getLength(n - 3)) return find(n - 3, k);
else return find(n - 2, k - getLength(n - 3));
}
int main() {
char c;
int m, N, i;
ll k;
scanf("%d%d\n", &m, &N);
N -= 1;
switch (m) {
case 1:
printf("%lld", getLength(N));
break;
case 2:
scanf("%lld", &k);
printf("%c", find(N, k - 1));
break;
case 3:
scanf("%c", &c);
getLength(N);
i = c == 'X' ? 0 : (c == 'Y' ? 1 : 2);
printf("%lld", dpCnt[N][i]);
break;
}
return 0;
}
= XF, 
= FY라고 합시다.
은 정가운데에 있는 문자가 '+'인 군을 뜻하고, 
은 정가운데에 있는 문자가 '-'인 군을 뜻하는 걸로 정의해봅시다.
를 나타내고, 음부호 문자열을 가지는 
의 문자열을 가지게 됩니다.
"? Are you busy? Will you send "
a
a
, 'c'인 군은 
의 문자열을 가지게 됩니다.
의 길이 La[i]와 
의 길이 Lb[i]는 아래처럼 정의됩니다.
