BOJ 8481. Generator

제목만 들어도 모두가 아는 이 전설의 문제는 ONTAK 2010에 출제된 문제다. ONTAK은 폴란드 국가대표 선발 캠프라고 알고 있는데, 자세한 내용은 찾아도 잘 안 나와서 딱히 깊이 알고 있지는 않다.

문제는 단순하다. 10개의 파일이 있고, 정수 하나를 입력받아 $(0 \le N \le 10)$ 그저 대응되는 파일의 내용을 출력하기만 하면 된다. 단 코드의 길이는 10만 바이트를 넘을 수 없고, 출력 파일은 예제 파일 $(N = 0)$을 제외하고 모두 20만 바이트를 가뿐히 넘는다는 게 특징.

gen0.out

그냥 출력하면 된다.

gen1.out

파일이 너무 커서 웬만한 프로그램으로 열려고 해도 열기 힘들다. 경험상 Visual Studio Code가 이럴 때 정말 좋은 역할을 해 준다.

파일을 열어 보면, 어떤 특정한 문자가 여러 개 (조금 많이) 써 있는 패턴만 반복된다는 것을 알 수 있다. 간단한 코드를 짜서 어떤 문자가 얼마만큼 반복되는지를 구해 주자. 이 데이터를 코드에 넣어 준 다음에, 실제로 출력할 때는 이 데이터를 바탕으로 그대로 출력하면 된다. 파일을 파싱해 보면 약 2081개의 구간이 있고, 이것을 코드에 집어넣으면 아무리 짧아도 1만 바이트가 넘는 길이가 필요할 것이다. 나는 이 부분에서 약 20000B를 사용했다.

gen2.out

문제를 열어 보면 피보나치 수열이 있음을 확인할 수 있는데, 뭔가 이상하다. 어떤 modulo가 있음을 추측할 수 있다. 그 modulo가 9099099909999099999임을 확인할 수 있다. 총 1만 개의 항이 출력되고 마지막에는 0.이 출력된다. 여기까지 알아냈으면 그냥 이걸 그대로 하면 되는데, 다만 피보나치 수의 항을 계산할 때 (a+b) % MOD 식으로 계산하면 이미 a+b에서 오버플로우가 나 버린다. unsigned long long을 쓰는 것이 좋다. 이 부분은 코드가 짧다.

gen3.out

$N = 2^{10}$인 시에르핀스키 삼각형과 비슷한 것을 출력하면 된다. 이러한 구조는 보통 재귀 함수를 이용해 만들게 되고, 이 문제에서도 재귀 함수를 이용한 분할 정복으로 쉽게 시에르핀스키 삼각형을 만들 수 있다. 당연히도, 출력을 배열에 저장해둔 뒤 나중에 한번에 출력하는 것이 구현상 유리하다. 자세한 풀이는 분할 정복류 별찍기 문제들을 참고하면 좋다만…

여기서 끝이 아니다. 이 데이터부터는 출제자가 의도적으로 쳐 놓은 장난들이 있다. 512줄 근처에서 특별한 메시지를 볼 수 있다. 정도껏 잘 처리하자.

gen4.out

여기서부터는 출력 파일의 규칙을 찾는 것부터가 어렵다. 규칙을 정리하면 $2$부터 $400 , 001$까지의 수들 각각에 대해 소수이면 $0$, 아니면 $1$을 형식에 맞게 출력하면 된다. 에라토스테네스의 체를 이용하면 쉽게 해결할 수 있다.

이 데이터 역시 3333줄 근처에 이상한 부분이 하나 있다.

gen5.out

이 출력 파일은 2000년 1월 1일부터 2020년 12월 31일까지의 날짜들에 대한 설명을 각각 폴란드어로 써 둔 것이다. 잘 보면 각 문장이 아래와 같은 형태를 하고 있다.

[일 이름] [달 이름] to [서수] dzien roku [연 이름].

줄 자체는 정말 많지만, 상응하는 부분들의 텍스트 가짓수만 보면 그리 많지 않다. 각각 31가지, 12가지, 366가지, 21가지밖에 존재하지 않는다. 따라서 이런 부분의 텍스트만 기존 파일에서 파싱해서 저장해 두면 문제없이 출력할 수 있다. 윤년 규칙에 따르는 것을 잊지 말자.

다음 사실을 활용하면 도움이 된다.

• 각 줄의 문자열을 to, dzien roku 기준으로 자르면 문자열을 세 부분으로 나눌 수 있다. (자를 때 양옆에 공백도 붙여주는 것이 좋다)
• 첫 번째 부분문자열에서, 달 이름은 항상 한 단어이므로, 마지막 공백을 기준으로 일 이름과 달 이름을 구분할 수 있다.
• 만우절과 어린이날을 조심하자.

나는 이 부분에서 약 12000B를 사용했다.

gen6.out

이 데이터는 $1$부터 $20 , 000$까지의 정수 $i$에 대해 $T[i^4 ] = S_i$ 형식으로 출력하면 된다. $S_i$를 알아내는 게 조금 까다로운데, 결론적으로 말하자면 소문자 알파벳으로만 이루어진 문자열을 모두 모아 길이순으로 (길이가 같으면 사전순으로) 정렬했을 때 $i^4$번째 문자열이다.

각 문자열을 구하는 것은 재귀 함수든 뭐든 사용하면 어렵지 않으므로, 문제를 쉽게 해결할 수 있을 것 같지만, 역시 10000번째 줄에 이상한 부분이 있다. 잘 처리하자.

gen7.out

패턴이 굉장히 난해한데, 수들을 #과 .로 그려 놓았다. 첫 몇 개의 수들을 적어 보면 1, 2, 11, 22, 121, 2101, 1012, 20211, 111001, …이다. 이를 통해 이 수들이 3진법으로 $2^n$들을 거꾸로 적어 놓은 것이라는 것을 알 수 있다. 이 작업을 $2^0$부터 $2^{170}$까지 먼저 해 준다. 다음으로, 마지막 네 줄을 출력해야 하는데, 이 네 줄은 사전에 파싱 프로그램을 돌려 어떤 수들을 출력해야 하는지 구해 놓는 것이 편하다. 마지막 줄 근처에 9099099909999099999가 또 있다는 사실에 주의하자.

gen8.out

이 문제는 .와 #로 웬 나선을 그려야 하는 문제이다. 처음 보면 진짜 답이 없다는 것을 느낄 수 있다. 그러나 #의 개수가 $30 , 506$개로 .보다 월등히 적기에 이들의 위치를 개별적으로 저장한다는 아이디어를 낼 수 있다. 시작점부터 시작해서 #의 위치를 추적하면, 다음 #가 항상 주변 8칸 중 하나에 등장한다는 것을 알 수 있다. 그래서 이 정보를 저장하면 약 3만 바이트 정도를 이용해 답을 구할 수 있다. 두 자리씩 정보를 묶어서 저장하면 이를 1만 5천 바이트 정도로 줄일 수 있다. 다행히 이 문제 데이터에는 장난질(?)이 없다.

gen9.out

주어진 그림을 적은 개수의 선분으로 표현하면 된다. 일단 2칸 이상 가로/세로/대각선 방향으로 연속한 것을 모두 선분으로 잡은 뒤, 길이가 긴 선분부터 색칠해 나가며, 만약 어떤 선분의 모든 칸이 이미 색칠되어 있다면 해당 선분을 제거해 주면 된다. 이렇게 했을 때 필요해지는 선분의 개수는 277개이다. 한 선분은 그 시작점, 끝점, 길이로 나타낼 수 있고(방향은 4가지밖에 없으니, 4가지 문자열로 나누어 저장하면 된다) 각 선분은 약 $1003^3$개 정도의 경우의 수를 가지고 있으므로 $64^5$, 즉 5바이트 안에 압축할 수 있다. 이렇게 하면 1500바이트 안쪽으로 전체 데이터를 인코딩할 수 있다.

gen10.out

규칙은 문제에 적어 줬으나 그 출력 양식이 난해해서 어려운 문제이다. 규칙을 파악해야 하는 부분은 행렬 $A$의 구조와, 행렬 $B$가 $A$로부터 어떻게 유도되는지이다. 행렬 $A$의 원소들을 왼쪽 위부터 차례대로 읽으면 항상 같은 수열의 접두사라는 것을 알 수 있는데, 이 수열의 길이가 4900이므로 저장해줄 수 있다. $B_i = A_i^n$이라는 관계식이 텍스트에 써 있는데, 저 $n$의 값은 직접 찾아 주어야 한다. 나는 $n$ 값을 효율적으로 찾는 걸 실패해서, $B$를 이진수열로 압축했다. 여기에 한 3만 바이트 정도가 들었다.

총평

전체적으로 재미있는 문제였다. gen10.out에서 $n$을 찾는 방법이 궁금해졌는데, 리프가 90990 어쩌고 하는 그 수라고 알려 줬다. 별개로 중간중간에 이상한 메시지만 안 넣었으면 더 재미있었을 것 같다.