Generator 문제 풀이 / 후기 (스포일러 주의)
개요
Generator 문제는 수많은 PS 문제들 중에서도 오로지 ‘구현’만으로 악랄한 난이도를 성립시킨 것으로 유명합니다. solved.ac 기준 Diamond III라는 상당한 고난도의 평가를 받고 있지만 이 문제를 풀기 위한 사전 지식이나 개별 테크닉은 높아야 Platinum 중상위권으로 생각하며, 문제의 난이도는 대부분 구현, 관찰, 그리고 요구하는 끈기와 인내심에 의해 결정된다는 점에서 다른 구현 위주의 고난도 문제들과는 차별이 되는 문제입니다.1
최근 문제 풀이를 연습할 시간이 부족했던 저에게 갑자기 이 문제를 당일치기로 풀어내는 것은 상당히 어려운 일이었고, 비록 주말이긴 했으나 거의 밤을 새는 바람에 생활 리듬도 한동안 흐트러지고 말았습니다. 이번 글에서는 이 악독한 문제를 푸는 동안의 생각 과정과 겪었던 일들을 소개해보고자 합니다.
풀이 과정을 직접적으로 담고 있기 때문에 문제를 직접 해결해보고 싶은 분들은 가급적이면 이후 내용을 읽지 않기를 권장합니다.
문제 내용
문제의 디스크립션은 간단합니다. 예제를 포함한 11개의 파일이 0번부터 10번까지 제공되고, 입력으로 해당 번호가 주어졌을 때 그 번호에 해당하는 파일 내용을 그대로 출력하는 프로그램을 작성하면 됩니다. 이렇게만 보면 정말 쉬운 문제입니다. 그냥 파일 내용을 복사해서 코드에 넣고 번호에 맞게 출력만 시키면 되기 때문입니다.
하지만 한 가지 조건이 더 있습니다. 바로 코드의 길이는 10만 바이트를 넘을 수 없다는 점입니다. 그런데 제공되는 파일은 무려 8 메가바이트가 넘어가며, zip으로 최대한 압축해 보아도 약 70만 바이트로 역시 10만 바이트 내에 구현해내기에는 역부족입니다. 일반적인 압축 기술만으로는 해결이 되지 않을 수준의 파일 크기입니다.
다행히도, 이 파일들을 메모장으로 열어보면 어떤 식으로 접근해야 하는지 알아내는 것은 그다지 어렵지 않습니다. 문제마다 비교적 명확해 보이는 패턴이 존재하기 때문입니다. 이 패턴을 분석하여 더 짧은 코드로 그 패턴을 재현해내도록 하는 것이 문제 해결의 핵심입니다.
준비
11개의 독립된 문제를 풀어야 하기 때문에, 각 문제에 대한 해결 과정을 최대한 분리하는 것이 필요했습니다. namespace같은 것을 활용하면 더 안전했겠으나, 사용이 익숙치 않았기에 대신 다음과 같은 규칙을 적용했습니다.
- 각 문제의 해결은 그 문제에 대한
solve함수 내에서2 - 프로그램 실행 도중 값이 변해야 하는 것은 가급적이면 지역 변수로
- 전역 변수 사용 시에는 항상 변수 이름의 뒤에 문제 번호를 붙이기 (
char a8[1005][1005];등)3
main 함수는 다음과 같이 작성하였습니다.
int main()
{
int n;
cin >> n;
switch (n)
{
case 0: solve0(); break;
case 1: solve1(); break;
case 2: solve2(); break;
case 3: solve3(); break;
case 4: solve4(); break;
case 5: solve5(); break;
case 6: solve6(); break;
case 7: solve7(); break;
case 8: solve8(); break;
case 9: solve9(); break;
case 10: solve10(); break;
}
}
0. “예제”, 난이도: 없음
말 그대로 예제입니다. 한 줄짜리 문자열 ONTAK 2010을 그대로 출력하면 됩니다.
void solve0()
{
cout << "ONTAK 2010\n";
}
1. “글자 반복”, 난이도: 쉬움
이 파일은 열어보면 특징이 한 눈에 들어옵니다. 같은 글자가 연속으로 아주 많이 나타나고 있다는 점입니다. 이를 간단한 프로그램을 작성하여 (글자의 종류, 글자의 연속된 개수) 쌍으로 묶어보면 원래의 글은 단 2081자밖에 되지 않는 것을 확인할 수 있습니다. 조금 더 글자 수가 적은 효율적인 DB를 만들기 위해 글자들이 나타나는 순서대로 하나의 문자열을 만들고, 각각의 개수를 저장하는 배열을 따로 만들었습니다. 추가적인 압축 과정은 거치지 않고 평범한 문자열 / 배열로 구현했습니다.4
string s1 = "Godzila terorizes Bajtoly lower again. (생략)";
vector<int> v1 = "{ 2932,2931,2928,2923,2916,5803,2883,2868,2851,2832,5599,2763,(생략)}";
간단하게 아래와 같은 코드로 이와 같은 정보를 생성할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int c;
int prev = 0;
int cnt = 0;
string s;
vector<int> v;
while ((c = getchar()) != EOF)
{
if (c == prev)
cnt++;
else
{
if (cnt)
{
s += char(prev);
v.push_back(cnt);
}
prev = c;
cnt = 1;
}
}
cout << "string s1 = \"" << s << "\";\n";
cout << "vector<int> v1 = {";
for (int x : v)
cout << x << ",";
cout << "};\n";
}
이제 이것을 s1의 각 글자에 대해 v1에 쓰인 개수만큼 출력하도록 코드를 작성하면 됩니다.
void solve1()
{
for (int i = 0; i < (int)s1.size(); i++)
for (int j = 0; j < v1[i]; j++)
cout << s1[i];
cout << '\n';
}
2. “피보나치 수”, 난이도: 쉬움
2번 파일도 열자마자 우리에게 익숙한 수열이 바로 눈에 들어옵니다. 1, 1, 2, 3, 5, 8, 13으로 시작하는, 바로 피보나치 수열입니다. 그런데 조금 아래로 내려보면 이상한 점이 눈에 띕니다. 수가 중도부터 더 커지지 않고 비슷한 길이를 유지하면서 커졌다 작아졌다 하는 것을 볼 수 있습니다. 여기서부터 본격적인 패턴 분석 능력을 시험받게 됩니다.
우선 수열이 처음으로 더 커지지 않고 줄어드는, 즉, 그 항이 이전 두 항의 합이 아닌 부분을 찾아볼 수 있습니다. 그러면 다음과 같은 지점을 찾아낼 수 있습니다.
4660046610375530309, 7540113804746346429, 3101060505122776739
이전 두 항이 4660046610375530309, 7540113804746346429라면 그 다음 항은 원래 12200160415121876738이 되어야 하는데 3101060505122776739이라는 다소 엉뚱한 수가 나타납니다. 그렇다면 원래 되어야 할 값과 실제로 쓰인 값 사이에 어떤 관계가 있을까요? 두 수의 차이를 구해보면 다음과 같습니다.
12200160415121876738 - 3101060505122776739 = 9099099909999099999
매우 인위적으로 만들어진 듯한 수가 나타났습니다. 이 차이가 이후 수열들에도 그대로 적용될까요? 그렇습니다. 정확히는 모든 수들은 원래의 피보나치 수에서 9099099909999099999로 모듈로 처리된 상태입니다. 이를 그대로 구현해주기만 하면 이 문제 역시 해결입니다.
void solve2()
{
ull x = 1, y = 1;
while (true)
{
cout << x << ", ";
if (x == 7829980104375723633ull)
break;
ull z = (x + y) % 9099099909999099999ull;
x = y;
y = z;
};
cout << "0.";
}
3. “별 샵 찍기”, 난이도: 쉬움
3번 역시 비교적 전형적인 별(실제로는 샵이지만) 찍기 문제임을 유추할 수 있습니다. 메모장으로 열고 최대한 축소해서 보면 BOJ의 별 찍기 - 11과 매우 유사한 형태인 것이 보이며 간단한 재귀를 통해 문제를 해결할 수 있습니다.
이 문제에서 처음으로 ‘함정’이 소개되는데, 전체적인 패턴만을 보고 구현하면 반드시 놓치게 되는 부분이 있습니다. 파일의 중간 부분에 가장 넓은 빈 삼각형의 우측 하단에 ‘ONTAK 2010’이라고 #들로 쓰인 부분이 있어, 이 부분에 대한 예외 처리를 추가해주어야 정답을 받을 수 있습니다. 저는 이 부분에 대한 처리를 위해 다음과 같은 코드를 작성했습니다.
const int sz3 = 1024;
char s3[sz3][sz3];
char s3_ex[5][sz3] = { "##..##.......(생략)",
(생략),};
void f3(int y, int x, int sz)
{
if (sz == 1)
{
s3[y][x] = '#';
return;
}
int hy = (y + y + sz) / 2;
int hx = (x + x + sz) / 2;
f3(y, x, sz / 2);
f3(y, hx, sz / 2);
f3(hy, x, sz / 2);
}
void solve3()
{
f3(0, 0, sz3);
for (int i = 0; i < sz3; i++)
{
if (i >= 506 && i <= 510)
{
cout << s3_ex[i - 506] << '\n';
continue;
}
for (int j = 0; j < sz3 - i; j++)
cout << (s3[i][j] == '#' ? '#' : '.');
cout << '\n';
}
}
기본적인 루틴은 f3 함수에서 재귀적으로 처리하되, 이후 실제로 출력할 때 이 ONTAK 2010이 쓰인 줄들은 별도로 DB를 만들어 (s3_ex) 예외적으로 출력하도록 해주었습니다.
4. “에라토스테네스의 체”, 난이도: 보통
이 글을 쓰는 지금 가장 자괴감을 들게 만드는 문제입니다. 이 패턴을 왜 당시에 인지하지 못했을까요?
간단히 할 수 있는 관찰은 0은 맨 처음을 제외하고는 홀수 번째에 나타나지 않으며, 1이 0보다 훨씬 많고 뒤로 갈수록 빈도가 높아진다는 점입니다. 여기까지만 봤을 때에도 유추가 되었어야 했는데, 이를 꽤 오래 보고도 생각해내지 못했던 것이 부끄럽습니다. 이 파일의 내용은 바로 각 수의 소수 여부를 2부터 차례대로 표시하는 문자열입니다.
이 관찰만 해낸다면 그 뒤는 어렵지 않습니다. 평범하게 에라토스테네스의 체를 실행하고, 이를 파일 형식에 맞게 80자씩 5000줄 출력을 하면 됩니다. 그런데 여기에도 이것만 하면 틀리게 되는데, 3334번째 줄에 또 하나의 함정이 숨겨져 있기 때문입니다. 위 3번 문제에서 나타났던 9099099909999099999가 이 줄에 뜬금없이 끼워져 있습니다. 이 함정을 찾기 위해 리눅스에서 diff를 돌려보았고, 이후 문제들에서도 종종 이 방법을 사용했습니다.
따라서 이 문제를 의도된 방법대로 풀기 위해서는 다음과 같이 할 수 있습니다.
void solve4()
{
vector<int> v(400005, 0);
for (int i = 2; i * i < 400005; i++)
{
if (v[i])
continue;
for (int j = i * i; j < 400005; j += i)
v[j] = 1;
}
v.erase(v.begin(), v.begin() + 2);
string sdf = "11111011909909990999909999911011111011101011101011111111111011111111101111111011";
for (int i = 0; i < (int)sdf.size(); i++)
v[i + 80 * 3333] = sdf[i] - '0';
for (int i = 0; i < 400000; i++)
{
cout << v[i];
if (i % 80 == 79)
cout << '\n';
}
}
하지만 저는 당시 이 패턴을 찾지 못했기 때문에, 수열 전체를 DB로 만드는 방법을 사용할 수밖에 없었습니다. 수열의 길이가 40만이기 때문에 평범하게 문자열로 넣는 것은 불가능했고, 그래서 1이 0보다 훨씬 많고, 홀수 번째 수가 처음을 제외하고는 모두 1이라는 점을 사용하여 ‘0 사이에 연속적으로 있는 1의 개수’들을 저장한 수열을 DB에 넣었습니다. 이것으로도 여전히 용량이 너무 컸기 때문에, 이 문제에서 처음으로 압축 기법까지 도입했습니다.
보다 효율적인 압축을 하려면 인터넷에서 코드를 찾아도 되었겠지만, 가능한 스스로 해결하고 싶었기에 적당한 수준의 압축을 위한 간단한 인코더 / 디코더를 작성했습니다. 이 인코더 / 디코더는 이후 다른 문제들에서도 압축을 위해 재활용했습니다.
int encode4(int n)
{
if (n <= 9)
return n + '0';
else if (n >= 10 && n <= 35)
return n + 'A' - 10;
else if (n >= 36 && n <= 61)
return n + 'a' - 36;
else if (n == 62)
return '#';
else
return '$';
}
int decode4(char c)
{
if (c >= '0' && c <= '9')
return c - '0';
else if (c >= 'A' && c <= 'Z')
return c - 'A' + 10;
else if (c >= 'a' && c <= 'z')
return c - 'a' + 36;
else if (c == '#')
return 62;
else
return 63;
}
인코더를 사용하여 이 파일을 미리 분석한 문자열을 코드에 삽입한 뒤, 프로그램 실행 시에 디코딩하여 원래의 수열을 복원했습니다. 그때의 코드는 다음과 같습니다.
string s4[] = { "000101012021012202...(생략)" };
void solve4()
{
vector<int> v;
string s;
for (string t : s4)
s += t;
for (char c : s)
{
int x = decode4(c);
for (int i = 0; i < x; i++)
{
v.push_back(1);
v.push_back(1);
}
v.push_back(1);
v.push_back(0);
}
v[0] = 0;
string sdf = "11111011909909990999909999911011111011101011101011111111111011111111101111111011";
for (int i = 0; i < (int)sdf.size(); i++)
v[i + 80 * 3333] = sdf[i] - '0';
v.pop_back();
v.pop_back();
for (int i = 0; i < (int)v.size(); i++)
{
cout << v[i];
if (i % 80 == 79)
cout << '\n';
}
}
5. “폴란드어 달력”, 난이도: 어려움
가장 재미없고 노가다를 요구하는 문제입니다. 파일을 열어보면 폴란드어를 모르는 사람에게는 도저히 의미를 알 수 없는 문장들이 한 줄에 하나씩 쓰여있는데, 이를 번역기를 이용해 돌려보면 대충 “m월 d일은 y년의 n번째 날입니다”와 같은 문장이 2000년 1월 1일부터 순차적으로 있는 것임을 알 수 있습니다. 문제는 이 m, d, y, n 등이 아라비아 숫자가 아닌 전부 폴란드어로 쓰여있기 때문에 각 수에 대응하는 폴란드어 단어를 직접 써넣어야 한다는 점입니다. 특히 ‘m월’은 m이 수로 쓰이지 않고 영어의 January와 같이 각 월마다 이름도 따로 정해져 있습니다.
결국 다음과 같이 수를 나타내는 단어에 대한 DB를 만들고, 날짜를 하나씩 증가시켜가면서 년, 월, 일과 해당 연도에서의 몇 번째 일인지를 올바르게 출력하는 것이 문제 풀이의 전부입니다. 이 과정에는 윤년을 판단하여 2월 29일에 대한 처리를 하는 것도 포함됩니다.
영어와 같이 1~19까지와 20 이후의 표기법이 다르고, 정확히 100의 배수인 것과 아닌 것의 표기법이 다른 등 고려해야 할 요소가 많고, 여기에도 함정이 두 개나 숨어있어 찾아서 예외 처리를 하는 것까지 상당히 귀찮고 실수 없는 구현을 요구하는 문제라고 할 수 있습니다. 더군다나 폴란드어 화자가 아닌 우리에게는 그 까다로움이 몇 배가 되는 문제입니다.
string s5[] = {
"","pierwszy","drugi","trzeci","czwarty","piaty","szosty","siodmy","osmy","dziewiaty","dziesiaty","jedenasty","dwunasty","trzynasty","czternasty","pietnasty","szesnasty","siedemnasty","osiemnasty","dziewietnasty"
};
string s5_10[] = {
"","","dwudziesty","trzydziesty","czterdziesty","piecdziesiaty","szescdziesiaty","siedemdziesiaty","osiemdziesiaty","dziewiecdziesiaty"
};
string s5_100_ex[] = {
"","setny","dwusetny","trzysetny"
};
string s5_100[] = {
"","sto","dwiescie","trzysta"
};
string s5_month[] = {
"","stycznia","lutego","marca","kwietnia","maja","czerwca","lipca","sierpnia","wrzesnia","pazdziernika","listopada","grudnia"
};
string s5_year[] = {
"dwutysiecznego","tysiace pierwszego","tysiace drugiego","tysiace trzeciego","tysiace czwartego","tysiace piatego","tysiace szostego","tysiace siodmego","tysiace osmego","tysiace dziewiatego","tysiace dziesiatego","tysiace jedenastego","tysiace dwunastego","tysiace trzynastego","tysiace czternastego","tysiace pietnastego","tysiace szesnastego","tysiace siedemnastego","tysiace osiemnastego","tysiace dziewietnastego","tysiace dwudziestego"
};
string n_to_s(int x)
{
if (x < 20)
return s5[x];
else
{
if (x < 100)
{
if (x % 10 == 0)
return s5_10[x / 10];
else
return s5_10[x / 10] + " " + s5[x % 10];
}
else
{
if (x % 100 == 0)
return s5_100_ex[x / 100];
else
{
string s = s5_100[x / 100] + " ";
x %= 100;
if (x < 20)
s += s5[x];
else if (x % 10 == 0)
s += s5_10[x / 10];
else
s += s5_10[x / 10] + " " + s5[x % 10];
return s;
}
}
}
}
void solve5()
{
int year = 2000, month = 1, day = 1, cnt = 1;
while (true)
{
string s;
if (year == 2007 && month == 4 && day == 1)
{
s = "Pierwszego kwietnia jest prima aprilis.\n";
}
else if (year == 2013 && month == 6 && day == 1)
{
s = "Pierwszego czerwca jest dzien dziecka.\n";
}
else
{
s = n_to_s(day) + " ";
s += s5_month[month] + " to " + n_to_s(cnt) + " dzien roku " + (year == 2000 ? "" : "dwa ") + s5_year[year - 2000] + ".\n";
}
if (month == 12 && day == 31)
{
year++;
month = 1;
day = 1;
cnt = 0;
}
else if (day == 31 || (day == 30 && (month == 4 || month == 6 || month == 9 || month == 11)))
{
month++;
day = 1;
}
else if (month == 2 && (day == 29 || (day == 28 && year % 4 != 0)))
{
month++;
day = 1;
}
else
day++;
cnt++;
s[0] = toupper(s[0]);
cout << s;
if (year == 2021)
break;
}
cout << "Koniec.\n";
}
6. “K번째 순열 찾기”, 난이도: 보통
이 문제는 가장 PS스러운 문제라고 할 수 있습니다. 두 가지의 패턴을 찾아야 하는데, 하나는 T[i]와 그에 해당하는 문자열의 관계를 알아내는 것이고, 다른 하나는 i가 증가하는 규칙이 무엇인지 찾는 것입니다.
각 항과 문자열의 관계를 찾는 것은 크게 어렵지는 않습니다. 수가 급격하게 커지는 것에 비해 문자열의 길이는 빠르게 증가하지 않는다는 점을 고려하면 모든 순열을 시도해보는 것이라고 쉽게 예측할 수 있고, 1번 “a”부터 차례대로 길이가 짧은 것부터, 길이가 같으면 사전순으로 나열해보면 16번째에 “bacd”가 나오는 것을 금방 찾을 수 있습니다. $k$가 주어졌을 때 $k$번째 순열을 찾는 문제는 순열의 순서 등 흔합니다. (남아있는 길이의 팩토리얼) $\times x$가 남은 $k$ 미만인 최대의 $x$를 찾아 남아있는 알파벳 중 $x$번째를 채워나가는 식으로 구현하면 됩니다.
i가 증가하는 규칙을 찾는 것도 어렵지 않습니다. 처음 몇 개의 수를 보면 문제를 풀 때 자주 볼 수 있는 제곱수들인 것을 볼 수 있는데, 좀 더 자세히 보면 그 제곱수 자체도 역시 제곱수이고, 이것이 1부터 차례대로 증가하는 수열인 것을 볼 수 있습니다. 즉, i번째 수는 i의 네제곱입니다.
이를 종합해서 코드로 구현하면 다음과 같습니다. 이 문제에도 함정이 하나 숨어있으니 잘 찾아내야 합니다.
ull fact(int x)
{
ull r = 1;
for (int i = 2; i <= x; i++)
r *= i;
return r;
}
void solve6()
{
ull i;
for (i = 1;; i++)
{
ull j = i * i * i * i;
ull n = j;
int len = 1;
while (fact(len) < n)
{
n -= fact(len);
len++;
}
vector<char> v;
for (int k = 0; k < len; k++)
v.push_back(char(k + 'a'));
string s;
for (int k = 0; k < len; k++)
{
int x = 1;
for (; x * fact(len - k - 1) < n; x++);
s += v[x - 1];
v.erase(v.begin() + x - 1);
n -= (x - 1) * fact(len - k - 1);
}
if (j == 10000000000000000ull)
cout << "T[10000000000000000]=\"9099099909999099999\"\n";
else
cout << "T[" << j << "]=\"" << s << "\"\n";
if (j == 160000000000000000ull)
break;
}
}
7. “2차원 문자열 읽기”, 난이도: 보통
5번보다는 낫지만 이 문제도 많은 귀찮음을 요구하는 구현 문제입니다. 네 종류의 글자 (‘0’, ‘1’, ‘2’, ‘,’)가 다섯 줄(+하나의 빈 줄)에 걸쳐 ‘그려진’ 문자열을 분석해야 합니다. 글자마다 폭이 다른데, 가장 두꺼운 글자는 좌우로 6칸을 차지하므로 이를 한 글자로 압축시킬 수 있다면 30배의 용량을 절약하게 되므로 이 문자열들을 분석하여 압축한 뒤 다시 복원해내야 합니다.
이 문제에서 조심해야 할 점은 다음과 같습니다.
- 글자마다 폭이 다르다.
- 중간에 한 줄이 아닌 두 줄을 건너뛰는 곳이 있다.
- 중간에 또 뜬금없는 9099099909999099999가 나타나는 곳이 한 군데 있다.
- 느닷없이 ‘,’가 아닌 ‘.’가 나타나는 곳이 한 군데 있고, 그 앞의 앞 공백 간격도 다르다.
전체적으로 보면 전광판의 숫자 문제와 유사하지만 요구하는 구현과 예외 처리가 많이 늘어난 것이라고 볼 수 있습니다. 이 문제의 데이터 파싱 프로그램은 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
string a[5][5] = {
{
".####.",
"##..##",
"##..##",
"##..##",
".####."
},
{
"###",
".##",
".##",
".##",
".##"
},
{
".####.",
"##..##",
"...##.",
".##...",
"######"
},
{
"..",
"..",
"..",
"##",
".#"
},
{
".####.",
"##..##",
".#####",
"....##",
".####."
}
};
int main()
{
string s[10];
vector<string> ans;
int cnt = 0;
while (cnt < 492)
{
int i;
for (i = 0; i < 6; i++)
{
cin >> s[i];
s[i] += ".......";
}
string t;
int j = 0;
while (j < 1000)
{
int k;
for (k = 0; k < 5; k++)
{
for (i = 0; i < 5; i++)
if (s[i].substr(j, a[k][i].size()) != a[k][i])
break;
if (i == 5)
break;
}
if (k == 5)
break;
t += char(k + '0');
int skip[5] = { 7, 4, 7, 6, 7 };
j += skip[k];
}
ans.push_back(t);
cnt += 6;
if (cnt == 468)
{
cin >> s[5];
cnt++;
}
}
cout << "string s7[] = {";
for (string t : ans)
{
cout << "\"" << t << "\",";
}
}
복원 코드는 다음과 같습니다.
string s7[] = { "1323113223121321013101232021131110013...(생략)" };
string a7[5][5] = {
{
".####.",
"##..##",
"##..##",
"##..##",
".####."
},
{
"###",
".##",
".##",
".##",
".##"
},
{
".####.",
"##..##",
"...##.",
".##...",
"######"
},
{
"..",
"..",
"..",
"##",
".#"
},
{
".####.",
"##..##",
".#####",
"....##",
".####."
}
};
void solve7()
{
int cnt = 0;
vector<string> ans(493);
for (int i = 0; i < 493; i++)
{
for (int j = 0; j < 1010; j++)
ans[i] += '.';
}
for (string s : s7)
{
int col = 0;
for (char c : s)
{
int i, j;
for (i = 0; i < 5; i++)
{
for (j = 0; j < (int)a7[c - '0'][i].size(); j++)
{
ans[cnt + i][col + j] = a7[c - '0'][i][j];
}
}
int skip[5] = { 7, 4, 7, 6, 7 };
col += skip[c - '0'];
}
cnt += 6;
if (cnt == 468)
cnt++;
}
ans[465][643] = ans[465][644] = ans[466][643] = ans[466][644] = '#';
for (int i = 0; i < 492; i++)
{
for (int j = 0; j < 1000; j++)
cout << ans[i][j];
cout << '\n';
}
}
8. “흔적 따라가며 압축하기”, 난이도: 어려움
이 문제는 압축에 초점을 많이 두는 문제입니다. 따라서 앞쪽 문제들에서 코드 길이를 많이 아꼈다면 상대적으로 더 쉬워질 수도 있습니다. 하지만 저는 이전 4번 문제 등에서 말리는 바람에 이미 남은 길이가 많지 않은 상태였기에 효율적으로 이 문제를 압축하느라 상당히 고생을 했습니다.
주어진 파일을 열어 축소해보면 ‘#’ 문자가 달팽이 모양으로 빙글빙글 돌면서 그려진 것을 볼 수 있습니다. 그런데 이것이 특별한 규칙이 있다면 참 좋을 텐데, “대략적으로” 시계방향으로 돌고 있다는 것을 제외하면 어떤 구체적인 패턴을 찾을 수 없다는 것이 문제입니다. 그렇다고 ‘#’이 나타나는 좌표를 전부 찾자니, 개수가 3만 개가 넘기 때문에 좌표 하나를 4바이트 내로 담는다고 해도 12만 바이트로 전체 글자 수 제한을 뛰어넘게 됩니다.
다행히 여기서는 조금 더 효율적인 방법이 있습니다. 바로 이 ‘#’들이 모두 한 줄로 쭉 이어져있다는 점을 이용하는 것입니다. 시작점으로부터 출발하면 다음 ‘#’이 있는 위치는 항상 상하좌우와 대각선까지 총 8가지 가능성밖에 없으므로, 하나의 ‘#’을 단 3비트만으로 표현할 수 있게 됩니다. 아까 4번 문제에서 만들어 둔 인코더 / 디코더를 사용하면 하나의 글자에 6비트 분량을 표현할 수 있으므로, 총 길이를 ‘#’ 개수의 반에 해당하는 바이트 수로 줄여낼 수 있습니다.
이 #의 발자취를 압축하는 프로그램은 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
char a[1005][1005];
int dy[]{ 1,1,1,0,0,-1,-1,-1 };
int dx[]{ 1,0,-1,1,-1,1,0,-1 };
set<pii> st;
int encode4(int n)
{
if (n <= 9)
return n + '0';
else if (n >= 10 && n <= 35)
return n + 'A' - 10;
else if (n >= 36 && n <= 61)
return n + 'a' - 36;
else if (n == 62)
return '#';
else
return '$';
}
int main()
{
int i, j;
for (i = 1; i <= 1000; i++)
cin >> a[i] + 1;
int y = 501, x = 501;
st.insert({ y, x });
vector<int> v;
while (true)
{
for (i = 0; i < 8; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (a[ny][nx] == '#' && st.find({ ny, nx }) == st.end())
{
y = ny;
x = nx;
st.insert({ y, x });
v.push_back(i);
break;
}
}
if (i == 8)
break;
}
string s;
for (i = 0; i < (int)v.size() - 1; i += 2)
{
int x = v[i] * 8 + v[i + 1];
s += char(encode4(x));
}
cout << "string s8 = \"" << s << "\";\n";
}
이 그림을 복원하는 코드는 다음과 같습니다.
string s8 = "0HIaadd$#tsrsrkjjhTRRRRR33300018919999A9HHIAII...(생략)";
char a8[1005][1005];
int dy[]{ 1,1,1,0,0,-1,-1,-1 };
int dx[]{ 1,0,-1,1,-1,1,0,-1 };
void solve8()
{
int y = 501, x = 501;
a8[y][x] = '#';
for (char c : s8)
{
int n = decode4(c);
int i = n / 8;
int j = n % 8;
y += dy[i];
x += dx[i];
a8[y][x] = '#';
y += dy[j];
x += dx[j];
a8[y][x] = '#';
}
a8[718][49] = '#';
for (int i = 1; i <= 1000; i++)
{
for (int j = 1; j <= 1000; j++)
cout << (a8[i][j] ? '#' : '.');
cout << '\n';
}
}
9. “선분 표현하기”, 난이도: 보통
8번과 비슷하지만 더 쉬운 문제입니다. 파일을 축소해서 보면 ‘#’들이 가로, 세로 또는 대각선 방향의 선분들을 표현하고 있는 것을 쉽게 파악할 수 있습니다. 따라서 모든 ‘#’의 위치를 개별적으로 표현하는 것보다는 각 선분의 시작점과 방향, 그리고 길이만을 저장해두는 것이 훨씬 압축 효율이 좋을 것이라고 예측할 수 있습니다.
다음과 같은 코드를 통해 이 과정을 구현할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
char a[1005][1005];
bool v[1005][1005];
int dy[]{ 1,1,0,1 };
int dx[]{ 1,0,1,-1 };
int main()
{
int i, j;
for (i = 1; i <= 1003; i++)
cin >> a[i] + 1;
cout << "vector<vector<int>> v9 = {";
for (i = 1; i <= 1003; i++)
{
for (j = 1; j <= 1003; j++)
{
if (a[i][j] == '#' && !v[i][j])
{
vector<int> len;
for (int k = 0; k < 4; k++)
{
int y = i, x = j;
do {
v[y][x] = true;
y += dy[k];
x += dx[k];
} while (a[y][x] == '#');
len.push_back(max(y - i, x - j));
}
cout << "{" << i << "," << j << "," << len[0] << "," << len[1] << "," << len[2] << "," << len[3] << "},";
}
}
}
cout << "};\n";
}
이제 이렇게 압축된 정보를 이용하여 원래 배열을 복원하여 출력하면 됩니다.
vector<vector<int>> v9 = { {2,813,2,2,1,131},{3,545,1,1,443,1},{14,489,1,1,48,1},...(생략) };
char a9[1005][1005];
int dy9[]{ 1,1,0,1 };
int dx9[]{ 1,0,1,-1 };
void solve9()
{
int i, j;
for (vector<int> v : v9)
{
int y = v[0], x = v[1];
for (int k = 0; k < 4; k++)
{
for (int p = 0; p < v[k + 2]; p++)
a9[y + dy9[k] * p][x + dx9[k] * p] = '#';
}
}
for (i = 1; i <= 1003; i++)
{
for (j = 1; j <= 1003; j++)
cout << (a9[i][j] ? '#' : '.');
cout << '\n';
}
}
10. “행렬 놀이”, 난이도: 매우 어려움
10번 문제는 마지막 문제답게 이전 문제들에 비해서는 훨씬 어렵습니다. 문제에서 무엇을 요구하는지 알아내는 것부터 시작해서 길이에 따른 출력 형식 조절 능력과 효율적인 압축을 위한 (제 능력으로는 여전히 알아내지 못한) 수학 지식까지 필요로 합니다. 이 문제도 앞선 문제들에서 바이트 수를 많이 아꼈다면 체감 난이도가 많이 내려갈 수도 있는데, 그 이유는 후술하겠습니다.
이 문제는 크게 두 부분으로 나뉘어 있습니다. 첫째는 수열 a_i를 a_1부터 a_15까지 차례대로 출력하는 부분입니다. 이 부분은 점화식이 주어져 있기 때문에 있는 그대로 구현하여 출력하면 되고, 들여쓰기와 줄바꿈에 유의만 하면 됩니다.
두 번째 부분을 풀기 위해서는 우선 처음에 주어진 식의 의미를 이해해야 하는데, 두 행렬 A_i와 B_i에 대해 A_i의 n제곱이 B_i와 모듈로 2로 같다고 합니다. 그러면 여기서 두 가지 의문점이 생기는데, 첫째로 A_i가 어떻게 만들어지는지에 대한 설명이 없으며, 둘쨰로 이 n이 무엇인지 힌트가 주어져있지 않습니다.
A_i를 만드는 방법은 위의 첫 부분과 연계지어 찾을 수 있습니다. a_i를 만드는 점화식을 따라 충분히 큰 i에 대한 a_i를 찾고, 이 수열의 원소를 차례대로 (행, 열)이 증가하는 순으로 채워넣은 것이 곧 A 행렬들입니다.
이제 가장 어려운 부분은 이를 통해 A_i에 n제곱 연산을 통해 B_i로 만드는 방법을 찾는 것입니다. 작은 i들에 대해 직접 행렬 제곱을 계산해보면, A_1부터 A_8까지 멋지게 세제곱에 B_i를 만들 수 있음을 확인할 수 있습니다. 그런데 고난은 여기서부터 시작됩니다. A_9부터 이 공식이 완전히 엇나가기 시작합니다. 브루트포스 코드를 작성하여 n을 1씩 증가시켜가면서 B_i가 될 때까지 찾아보면, A_9는 무려 117제곱, A_10은 112제곱을 해야 하며, A_30은 무려 6753123제곱, 그 이후에는 아무리 오랜 시간 연산을 해도 답이 나오지 않는 항까지 존재합니다.
이 n을 빠르게 찾아내는 방법은 저는 아직 알아내지 못했으나, 이 문제에서 영감을 얻어 만들어진 문제가 solved.ac 기준 Ruby II인 Binary Matrix 문제라고 합니다. 제 수학 실력으로는 답을 찾을 수 없었기에, 최대한 압축하여 DB를 만드는 수밖에 없었습니다.
우선 최대한 용량을 아끼기 위해 브루트포스를 통해 적당한 시간 내에 답이 나오는 것들은 모두 찾아두었습니다. 그래서 다음과 같은 코드를 작성하여 문제 해결을 위한 기초 배열을 만들었습니다. 다만 이 코드를 그대로 실행하면 마지막 항까지 적절한 시간 내에 도달하지 못하기 때문에, 실제 문제를 풀 때에는 멀티스레드로 모든 항을 동시에 계산하도록 하는 코드를 따로 작성하였습니다.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
vvi a10(31);
vvi ma[71], mb[71];
vvi mul(const vvi &a, const vvi &b)
{
vvi x = a;
for (int i = 0; i < (int)a.size(); i++)
for (int j = 0; j < (int)b[0].size(); j++)
{
x[i][j] = 0;
for (int k = 0; k < (int)b.size(); k++)
x[i][j] += a[i][k] * b[k][j];
x[i][j] %= 2;
}
return x;
}
int main()
{
int i, j, k;
vector<int> ans;
for (i = 1; i <= 70; i++)
{
vvi a(i), b(i);
for (j = 0; j < i; j++)
{
a[j].resize(i);
b[j].resize(i);
for (k = 0; k < i; k++)
cin >> a[j][k];
for (k = 0; k < i; k++)
cin >> b[j][k];
}
vvi c = a;
int cnt = 1;
while (c != b)
{
c = mul(c, a);
cnt++;
}
cerr << i << ' ' << cnt << '\n';
ans.push_back(cnt);
}
cout << "vector<int> m10 = {";
for (int x : ans)
cout << x << ",";
cout << "};\n";
}
vector<int> m10 = { -1,
1,2,2,3,3,3,2,3,117,112,
3,1509,5,12,11,9,9,3,207,1139,
4,112,459,39,4299,505104,8748,656829,3,6753123,
1248141,207,46359,6,1384,7,235931,2431119,230599,46359,
1761729, -1 ,5573484,1352154, -1 ,22899,5,21, -1 , -1 ,
20109, -1 , -1 ,1632111,6, -1 , -1 ,366, -1 , -1 ,
747, 8959052, -1, -1, -1, -1, -1, -1, -1, -1 };
-1로 표기된 것들은 답을 구하지 못해 포기한 부분입니다. 나머지들은 답을 구해서 최대한 압축을 시켰으니, 이제 남은 부분은 어쩔 수 없이 B_i 행렬째로 DB를 삽입해야 합니다. 그러나 저는 이 당시 이미 남은 바이트 여유가 많지 않았고, 답을 구하지 못한 항들이 대부분 뒤쪽이고 행렬의 크기는 그 제곱에 비례하기 때문에 이들에 대한 최대한의 압축이 필요했습니다.
다행히 B_i 행렬은 0과 1로만 이루어져 있었기 때문에, 위에서 만든 인코더 / 디코더를 사용해서 한 번에 6개 원소를 묶어서 처리할 수 있었습니다. 그렇게 크기를 줄여 모두 코드에 넣고, 미리 n을 계산한 항들은 빠른 행렬 거듭제곱을 이용하여 계산해주고, DB로 처리한 항은 그대로 출력하도록 코드를 작성했습니다.
using vi = vector<int>;
using vvi = vector<vi>;
vvi a10(31);
vvi ma[71], mb[71];
vector<int> m10 = { -1,
1,2,2,3,3,3,2,3,117,112,
3,1509,5,12,11,9,9,3,207,1139,
4,112,459,39,4299,505104,8748,656829,3,6753123,
1248141,207,46359,6,1384,7,235931,2431119,230599,46359,
1761729, -1 ,5573484,1352154, -1 ,22899,5,21, -1 , -1 ,
20109, -1 , -1 ,1632111,6, -1 , -1 ,366, -1 , -1 ,
747, 8959052, -1, -1, -1, -1, -1, -1, -1, -1 };
string mp10[71];
vvi mul(const vvi &a, const vvi &b)
{
vvi x = a;
for (int i = 0; i < (int)a.size(); i++)
for (int j = 0; j < (int)b[0].size(); j++)
{
x[i][j] = 0;
for (int k = 0; k < (int)b.size(); k++)
x[i][j] += a[i][k] * b[k][j];
x[i][j] %= 2;
}
return x;
}
vvi sq(const vvi &a, int n)
{
if (n == 1)
return a;
vvi x = sq(a, n / 2);
x = mul(x, x);
if (n % 2)
x = mul(x, a);
return x;
}
void f10(int n)
{
vvi &a = ma[n], &b = mb[n];
a.resize(n);
int i, j, cur = 0;
for (i = 0; i < n; i++)
{
a[i].resize(n);
for (j = 0; j < n; j++)
a[i][j] = a10[30][cur++];
}
if (m10[n] != -1)
b = sq(a, m10[n]);
else
{
queue<int> q;
for (char c : mp10[n])
{
int x = decode4(c);
for (i = 5; i >= 0; i--)
q.push(!!(x & (1 << i)));
}
b = a;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
b[i][j] = q.front();
q.pop();
}
}
}
void solve10()
{
mp10[42] = "qNa0k7HDGZltyq9vSx1Sd0sFFgK2...(생략)";
mp10[45] = ...
mp10[49] = ...
(생략)
mp10[70] = ...
cout << "a_i = a_{i-1} . a_{i-2}\n\n";
a10[1] = { 0 };
a10[2] = { 0, 1 };
int i, j;
for (i = 3; i <= 30; i++)
{
a10[i] = a10[i - 1];
for (int x : a10[i - 2])
a10[i].push_back(x);
}
for (i = 1; i <= 15; i++)
{
cout << "a_" << i << " = ";
for (j = 0; j < (int)a10[i].size(); j++)
{
if (j != 0 && j % 40 == 0)
{
for (int k = 0; k < 6; k++)
cout << " ";
if (i >= 10)
cout << " ";
}
cout << a10[i][j] << (j == (int)a10[i].size() - 1 ? '\n' : ' ');
if (j % 40 == 39)
cout << '\n';
}
cout << '\n';
}
cout << "\n(A_i)^n = B_i (mod 2)\n\n";
for (int n = 1; n <= 70; n++)
{
f10(n);
for (i = 0; i < n; i++)
{
if (i == n / 2)
cout << "A_" << n << " = ";
else
{
cout << " ";
if (n >= 10)
cout << " ";
}
for (j = 0; j < n; j++)
cout << ma[n][i][j] << ' ';
cout << " ";
if (i == n / 2)
cout << "B_" << n << " = ";
else
{
cout << " ";
if (n >= 10)
cout << " ";
}
for (j = 0; j < n; j++)
cout << mb[n][i][j] << (j == n - 1 ? '\n' : ' ');
}
cout << '\n';
}
}
이렇게 작성했더니 당시 코드 크기가 100000바이트를 살짝 넘었기에, 모든 들여쓰기를 제거하고 98937B로 첫 정답을 받았습니다. 이후 이 글을 쓰면서 4번 등에서의 개선을 거치고 나니 들여쓰기의 제거 없이도 65674B로 제법 여유 있는 양이 되었습니다.
전체 정답 코드는 http://boj.kr/da8fa9ae24f743e08c17b9dc8a2d9447 에서 보실 수 있습니다.
여담
사실 이 문제를 푸는 데에 필요했던 코딩의 상당량은 제출하지 않고 로컬에서만 실행한 프로그램을 작성하는 데에 있었습니다. 입력 파일들을 그 형식에 맞게 파싱하고, 패턴과 예외를 찾고, 압축하는 등의 과정이 매우 중요했기 때문입니다.
문제 1개를 풀어도 실수를 하기 쉬운데, 11개나 되는 복잡한 구현 문제들을 한 글자도 틀리지 않고 정답을 받는다는 것은 상상하기 어려웠기에 정답을 정교하게 비교해줄 프로그램도 필요했는데, 이는 그냥 BOJ Stack을 활용했습니다. 또한 정확히 어디에서 틀렸는지를 찾기 위해 리눅스의 diff도 유용하게 사용했습니다.
지금 돌이켜 보면 10번 문제를 제외하고는 어느 과정에서도 특별히 ‘어렵다’고 할 만한 것이 없었는데도 이렇게나 힘든 경험으로 기억하게 만들다니 정말 대단한 문제였던 것 같습니다.