[BOJ 8481] Generator, 희대의 구데기 문제를 풀어보았습니다.

오랜만입니다. 리유나입니다.

 

최근 꾸준히 앳코더나 코포는 참여했지만 본진인 BOJ를 그렇게 열심히 하진 않았는데, 간만에 삘을 받아버린 바람에 이참에 8481이나 풀어야겠다! 하고 몇년을 묵힌 8481에 도전을 했습니다! 아마 16일 걸렸네요...

너무나도 감개무량하네요 ㅎㅎ

1. 그래서 이게 무슨 문젠데?

한국 PS판에서는 "8481"이라고 하면 그 자체만으로 이미 너무나도 유명한 숫자입니다. 저 문제는 "ONTAK 2010"이라는, 당시 폴란드 IOI 국가대표를 선발하는 시험에 출제된 문제고, 내용은 너무나도 간단합니다. 주어지는 숫자 0에서 10까지에 대해, 정해진 아웃풋 파일과 똑같은 것을 출력하면 됩니다.

 

사실 그걸로 끝이면 아무리 생각해도 국대 선발 문제도, 다이아 3 문제도, 유명 구데기 문제도 아닐텐데, 도대체 왜 그런 일이 생겼냐고요?

 

그럼 아웃풋 파일 꼬라지(?)를 조금만 보고 옵시다.

4번 output입니다.

7번 output입니다.

네...대강 이런 식입니다. 딱봐도 구현하기도 출력하기도 너무 귀찮은 것들이 10개나 있네요.(0번은 그냥 "ONTAK 2010" 출력이라 논외) 나이브하게 출력하면 되는 거 아닌가 싶겠지만, 이 문제에는 또한 10만KB 제한이 있습니다. 당연히 그냥 출력하면 제한을 넘어도 한참 넘깁니다.

 

이 문제의 구데기성이 너무나도 유명해진 바람에, BOJ에서는 어째서인지 20000번 문제도, 30000번 문제도 이와 비슷한 형식의(더욱 어려운)문제로 출제되는 전통이 생겨버리고 말았습니다... 솔브드 티어로도, 실제로 푼 사람수도 20000번과 30000번이 8481보다 어려운 것은 확실합니다만, 그래도 여전히 8481은 이 분야의 원조로서의 악명이 높습니다.

어찌되었건 구현력도 늘리고, 업적 하나도 달성하는 느낌으로 치고, 교환학생 생활에서 비는 시간을 사용하는 겸해서 풀었습니다!

 

문제의 규칙이나 풀이는 사실 요즘은 찾아보면 잘 나와서, 저는 그것보다는 '그것들을 어떤 식으로 찾고 구현했는지에 대해서' 조금 설명해보려고 합니다.

 

2. 사전 준비

기껏 열심히 짰는데, 틀렸습니다가 나와버리면 가슴이 쓰라리겠죠... 심지어 어디서 몇번이 틀렸는지도 모르니깐 더더욱요.

다행히도 저희의 목적은 그냥 output 파일을 있는 그대로 출력하는 것이기 때문에, 저는 n에 따라 출력하는 파일을 로컬에 저장해두고 그 파일들과 원래 파일이 일치하는지 아닌지를 전부 검사하는 프로그램을 먼저 만들었습니다.

참고로 처음에는 BOJ 제출 몇 퍼센트까지 가는지 확인하는 방식으로도 검사해볼까 싶었는데, 이게 하필 4%에서 검사하는 데이터가 10번 데이터인 바람에(assert문으로 확인해봤습니다)순서대로 구현한다면 별로 쓸모없는 방법이네요...

대강 이런 느낌이네요.

이제 이 코드를 잘 통과하게끔 출력을 해주면 됩니다. 간단하죠? ㅎㅎ(??)

 

3. 구현

스포일러가 될 가능성이 다분하므로 펼치기/접기 기능을 통해서 각각의 테스트 케이스의 규칙과 처리 방법을 간략히 요약하겠습니다. 정말 핵심이 되는 부분은 직접 구현하시길 권장드리며, 다른 포스트들과는 달리 정답 소스 코드는 올리지 않겠습니다.(사실 일단 길이가 5만KB라서 올리기도 그래요...)

 

0번 데이터

ONTAK 2010을 출력하면 됩니다. 사실 이게 안돼서 8481에서 막히신 분들은 없으리라 믿습니다.

 

1번 데이터

이 문제에 처음 도전할 때부터 사람 진짜 당황하게 만드는 수많은 G들의 압박입니다. 같은 문자가 그냥 엄청 많이 나올 뿐이므로, 그 문자들이 몇번씩 반복되어서 나오는지를 확인하는 것이 중요합니다. 나이브하게 해보면 규칙이 있는 것 같다가도 좀 어긋나는 부분이 있는데, 사실 이는 output의 모체가 되는 영문 텍스트가 있고, 그것들을 전부 규칙에 맞게 차례차례 특정 글자수만큼 적은 것입니다. 어긋나는 부분은, 가령 room이라는 단어가 있다면 o를 n번 출력하고 그다음 o를 m번 출력해서, n+m이 나오기 때문입니다. 영문 텍스트를 먼저 대강 복구해보고, 조금 이레귤러하다 싶은 숫자들로 나오는 문자들은 아마도 두번 연속해서 나오는 것들이기 때문에 이런 것들을 잘 처리해주고, 그 텍스트를 규칙에 맞게 출력해주면 됩니다. 놀랍게도 이 길디긴 파일이 사실은 '딱 한 줄'입니다.

참고로 텍스트는 "Godzila terrorizes..."로 시작하는 것이 나온다면 옳게 구하신 것이며, 이는 동 대회에 나온 다른 문제의 본문을 변형시킨 것입니다.

 

2번 데이터

보면 금방 파악하실 수 있는 피보나치 수열입니다. 먼저 개수 확인을 해보고 한줄로 죽 출력하시면 되고, 실은 9099099909999099999로 나눈 나머지를 출력하는 것입니다. 이 숫자는 앞으로도 아주 자주 나오니까 미리 변수로 저장해 두시는 것을 추천드립니다.

 

3번 데이터

시어르핀스키 삼각형입니다. 1024*1024니까 재귀 열번 돌리셔도 되고, 실은 for문 두개 돌려서 i랑 j xor한 값으로도 시어르핀스키 삼각형을 표현할 수 있어서 이 방법을 사용하셔도 무방합니다.

다만 딱 중간 즈음에 누가 장난을 쳐놨습니다. 3번부터 7번 데이터까지는 꼭 이상한 이스터에그가 하나씩 있으니 잘 확인하셔야 합니다.

이 문제의 경우에는 여기입니다.

 

4번 데이터

처음 보면 규칙이 그렇게 쉽게 나오지는 않습니다. 1이 훨씬 많고 0이 처음을 제외하면 짝수번째만 나오는 점에서 생각해보면 눈치채실 수도 있는데, 2부터 시작해서 정수들이 소수인지 아닌지를 판별해서 소수면 0, 아니면 1을 출력하는 규칙입니다.

에라토스테네스의 체로 잘 해주면 문제없이 할 수 있습니다만, 그놈의 90990....이 어딘가 중간에 멋대로 끼어들어가 있습니다. 요 부분을 조심해서 처리해주시면 됩니다.

 

5번 데이터

상당히 애를 먹은 데이터입니다. 폴란드어를 할 줄 아신다면(??)규칙은 금방 보이시겠지만, 아니라면 슬프지만 직접 조사하셔야 합니다. 내용은 2000년 1월 1일은 2000년의 첫번째 날이다. 2000년 1월 2일은 2000년의 두번째 날이다... 와 같은 글이 2020년까지였나? 쭉 적혀있는 것입니다.

to, roku를 기준으로 파싱하고 폴란드어로 년, 월, 일, 서수를 어떻게 나타내는지를 조사하셔서 규칙을 찾으면 그런대로 풀 수 있다고 생각합니다. 마지막 줄에 Koniec.(끝)도 있습니다.

이 문제의 이스터에그는 중간에 두줄이 하나는 4월 1일이라서 만우절, 하나는 6월 1일이라서 국제 아동절(~=어린이날)이라고 따로 출력하는 부분이 있습니다. 규칙대로 출력하고 검사하면 틀리는 두 줄이 있을텐데, 그것만 따로 처리해주시면 됩니다.

저는 할줄 아는 폴란드어는 '지엔 도브리(좋은 아침)'랑 '지엥쿠예(감사합니다)'랑 쿠르바(욕설)정도밖에 없었는데 이것 때문에 강제로 폴란드어를 엄청 주입당했네요(ㅋㅋㅋ)

 

6번 데이터

왼쪽 숫자들은 딱 보면 네제곱수들이 나열된 것을 확인할 수 있습니다. 오른쪽이 문제인데, a의 모든 순열, ab의 모든 순열, abc의 모든 순열... 들을 차례차례 사전순으로 정렬하면 나오는 문자열들 중 (왼쪽숫자)번째 것을 출력하는 규칙입니다.

결국 오른쪽 순열을 구하는 구현을 하는게 조금 귀찮은 부분이 되는데, 1!, 2!, 3!...등을 0이나 음수가 되기 전까지 차례차례 빼면서 몇글자 짜리 문자열이 나오는지를 확인하고, 그 글자 문자열의 순열 중에서 (n-1!-2!-3!-...)번째 문자열이 무엇인지를 구하는 구현을 하면 됩니다. 방법은 여러가지 있을 것인데, 저는 abcd...의 순열이라면 a로 시작하는 것이 (n-1)!개, b로 시작하는 것이 (n-1)!개... 인 것을 활용해 첫 알파벳을 구하고 나머지는 재귀로 구하는 식으로 했습니다. 아마 다른 구현 방법도 꽤나 있으리라 생각합니다.

아 그리고, 1만번째 줄에 그놈의 90990...이 있습니다.

 

7번 데이터

우선 아스키 아트 같은 느낌으로 숫자들이 나열되어 있습니다. 딱 보면 삼진법으로 무언가를 나타낸 것은 알겠는데, 그대로 변환하면 1, 2, 4, 8, 16, 64, 32, 184...가 되어 규칙을 파악하기 어렵습니다.

사실 눈치가 빠르다면 앞 부분에서 알 수 있는데, 이는 실은 2의 n제곱을 삼진법으로 나타낸 뒤, 그것을 뒤집은 숫자들입니다.

그다음은 출력을 구현하는 부분인데, 은근히 까다롭습니다. 0, 1, 2, 쉼표, 띄어쓰기 등을 표현하는 함수들을 각각 만들고, 과정에서 줄바꿈이 일어날 거 같으면 그냥 바로 다음줄로 넘어가고, 이런 식으로 숫자들을 주르륵 출력해야 하는데 여간 귀찮은 일이 아닙니다.

그리고 마지막(아스키아트 기준)네 줄은 그냥 아무 숫자 대잔치인데, 처음에는 90990...을 삼진법으로 나타낸 건가 했는데 9의 배수가 아니라 그건 아닌 듯했고, 규칙은 따로 못 찾아서 요걸 아예 하드코딩해서 그대로 출력하거나, 10진법으로 변환 후 코드에 저장한 뒤 다시 3진법으로 변환해서 출력하거나 하면 됩니다.(저는 전자를 택했습니다 ㅎㅎ)

한가지 다행인 건, 이렇게 귀찮은 이스터에그가 포함되는 데이터는 여기까지입니다.

이 부분은 따로 규칙이 없습니다.

 

 

8번 데이터

여기서부터는 따로 이스터에그는 없지만 구현이 빡셉니다.

처음 보면 그냥 점들만 덩그러니 보일 수 있는데, 자세히 보면 500,500에서 시작해서 무언가 바깥으로 점점 꼬불꼬불 도는 꽈배기같은 모양이 나오는 것을 확인할 수 있습니다.

다행인 점은, #의 개수가 .에 비해 현저히 적고, #은 꼭 여덟 방향 중 한 방향으로는 이어져있는 형태입니다. 이를 이용해서 먼저 원래 파일을 들고 와서 500, 500에서 어느 방향으로 쭉 이어지는지 기록을 해두고 그것을 그대로 다시 출력하면 됩니다. 저는 각각의 방향을 0부터 7까지로 먼저 나타낸 뒤, 두개씩 합쳐서 64개의 문자 중 하나로 각각 대응시키는 방법을 사용했습니다. 이렇게 하면 문자열의 길이를 절반으로 줄일 수 있어서 코드 길이를 아끼는 데에 도움이 됩니다.

 

9번 데이터

제 개인적으로는 5번과 함께 가장 애먹었던 데이터입니다. 5번은 언어의 장벽이었으니 실질적으로는 가장 짜증났던 부분이네요.

1003*1003 좌표 평면에 x축, y축에 평행하거나 기울기가 1, -1인 선분들이 잔뜩 있습니다. 다행히도 이번에도 선분의 개수가 그렇게 많지는 않아서 모든 선분을 미리 다 찾아두고 계산하면 됩니다. 기울기/시작점/끝점/길이를 적당히 잘 나타내면 되는데, 모든 선분을 1003*1003*1003*4가지의 방법으로 나타낼 수 있고, 이게 대강 84^5보다 조금 작아서 저는 84개의 문자들을 이용해서 각각의 선분을 84진법으로 다섯글자로 나타냈습니다. 이정도로 열심히 압축 안하면 이 부분에서 길이 초과가 나기 십상입니다.

저는 처음에는 조금 나이브하게 '어떤 부분에 #가 있고, 그 옆에 또 #가 있으면 무조건 다 선분이다.'로 처리했는데, 이 경우에는

##

# .

과 같이 두 선분이 만나는 지점에서 실제로는 처리하지 않아도 되는 쓸데없는 선분이 너무 많이 발생한다는 문제가 있었습니다. 그래서 이렇게 처리했을 때에는 선분이 다 합쳐 6천개 가량 나왔고 압축도 위 보다는 조금 널널하게 해버린 바람에 얄짤없이 길이초과가 떴습니다. 잘 관찰해보면 모든 선분은 길이가 3 이상이라서(증명 안하고 풀었는데 맞더라고요...)오른쪽/아랫쪽/오른쪽아래/왼쪽아래로 가면서 나이브하게 선분들을 모두 조사하되 길이가 3 이상인 것들만 저장하는 식으로 해서 선분의 개수를 1000개 미만으로 크게 줄일 수 있었습니다. 따라서 모든 선분의 데이터를 저장해도 길이 5000짜리 string 하나 나올 뿐이라 제한에 안 걸릴 수 있었습니다.

 

10번 데이터

이쪽은 생각만큼 어렵지는 않습니다. 먼저 처음 나오는 a_n의 규칙은 관찰로 금방 찾을 수 있는데, 대강 피보나치와 같은 느낌이라고 생각하시면 됩니다. 조금 더 엄밀하게는, a_n=a_n-1+a_n-2로도 표현할 수 있겠네요. 이것으로 a_15까지 구하는 것은 그렇게 어렵지 않습니다. 오히려 출력 형식 맞춰서 출력하는 게 약간 귀찮을 수 있겠네요.

다음은 A^n=B 라는 행렬 거듭제곱 식이 나옵니다. A 행렬은 보면 맨 왼쪽 위부터 차례대로 위에서 구한 a 수열의 수들이라는 것을 확인할 수 있고,(a_n들은 모두 prefix가 같기 때문에 아무 a_n에 대해서 잡고 구해도 됩니다.)B는 그것을 n제곱 한 뒤 mod 2를 한 결과입니다...만 n이 무엇인지 안 나와있죠.

n을 직접 구하는 것이 조금 어렵고, 사실 행렬이 70개밖에 없는데다 전부 0 아니면 1이라 B는 깡으로 해싱하고 8번이나 9번처럼 직접 문자열을 넣어서 풀어도 됩니다. n에 대해서 힌트를 조금 드리자면, 이 문제를 여기까지 정직하게 푸셨다면 제일 의심되는 조금 많이 큰 숫자가 하나 있을거라 생각합니다.(ㅎㅎ)

행렬 거듭제곱이야 구현하면 되고, 시간 복잡도는 O(70^4logn)이 걸리는데,(헁렬곱이 70^3logn, 그게 1번부터 70번까지 있으니깐)n이 꽤 큰 값인지라 솔직히 저는 로컬에서 구동했을 때 거의 20초 넘게 걸려서 '아...제출해보고 안되면 그냥 하드코딩해야겠다'하고 생각했는데 의외로 바로 맞았습니다. 의외로 이것 또한 행렬들을 출력형식 맞춰서 출력하는 게 또한 고통입니다만, 뭐 이정도 처리는...여기까지 오실 정도라면 구현하실 수 있으리라 믿습니다.

4. 후기

솔직히(당시 기준으로도, 지금으로도)엄청나게 새로운 컨셉의 신선한 문제라고 생각합니다, 사실 따지고 보면 별찍기 같은 것들의 극한의 업그레이드 버전인 거잖아요. 그런 점에서는 꽤 재미있지 않았나 싶어요. 여러 데이터들을 압축하는 방법에 대해서도 생각하게 해주는 부분이 CS적으로도 의외로 좋다고 생각해요. 이 문제의 그런 점이 많은 사람들을 유혹하는 거겠죠?(아니면 그냥 다이아 3이라 레이팅으로 유혹하는 걸지도...)

다만 좀 지나칠 정도로 귀찮은 게 흠이라면 흠이었습니다. 출력이 귀찮은 문제도 있었고, (당연히 폴란드 내부 대회니까 신경은 안 썼겠지만)언어의 장벽이 크게 다가오는 문제도 있고, 그놈의 90990...이나 ontak 2010같은 걸 이상한데 슉슉 끼워넣어서 귀찮은 것도 있고... 제가 솔직히 실제 대회나 캠프에서 저런 문제 봤으면 욕 거하게 했을 것 같아요.() 사실 문제 풀면서 내내 고통받으면서, '솔직히 이건 당시 폴란드의 고위자제 누군가를 IOI에 보내기 위해서 비리가 있었던 게 아닐까'라는 생각을 반농반진으로 했습니다 ㅋㅋ...

뭐... 그래도 정말 끝내니까 뿌듯하네요. 정말 언젠가는 20000번이나 30000번도 풀어보고 싶지만, 아직 제게는 무리가 아닐까 싶습니다 ㅎㅎ... 혹시 더 궁금하신 점이 있으시면 편히 댓글로 여쭤봐 주세요. 긴글 읽어주셔서 감사합니다!

솔직히 태그 더 달만한 거 있지 않을까 싶은데, 당장 생각나는 것들은 저정도네요 ㅋㅋ.