백준 8481번 풀이 (Generator)

http://boj.kr/8481 

8481번: Generator

solved.ac 티어: D3

 

다3짜리 구현(+규칙찾기)문제다 ㅋㅋ;

계속 플래~다이아만 밀다보니까 머리도 아프고 문제도 잘 안 풀려서 잠깐 휴식하면서 구현 연습하려고 이 문제를 풀기 시작했는데 절반쯤 풀었을때부터 후회되기 시작했다. ㅋㅋㅋㅋㅋ

 

이 문제 풀지 마세요

 

풀이)

데이터 분석을 하기 위해 파일 입출력으로 파일을 뜯어보고 푸는 것을 추천한다. 그리고 체커를 만들어서 출력한 파일이 원래 파일과 동일한지 꼭 확인해봐야 한다. 파일 곳곳에 이스터에그가 숨어있어서 틀릴 가능성이 매우 높기 때문이다.

데이터 0

그냥 예제 출력하면 된다.

 

데이터 1

데이터를 보면 같은 문자가 엄청 많은 개수로 연속되어 있다는 것을 확인할 수 있다. 문자 개수를 카운팅해서 나열해보면 계차수열이 나오게 된다.

 

데이터 2

피보나치 수열이다. 잘 계산해보면 mod 값이 9099099909999099999라는 것을 알 수 있다.

 

데이터 3

시어핀스키 삼각형이다. 크기 1024짜리 시어핀스키 삼각형을 출력하면 된다.

 

중간에 이스터에그로 ONTAK 2010이라는 문구가 #으로 찍혀있다.

 

데이터 4

여기부턴 규칙이 자명하지가 않다. 처음에 좀 뻘짓을 많이 했는데 규칙을 잘 찾아보면 2부터 숫자를 나열했을 때 소수는 0, 합성수는 1로 표시하는 규칙이다.

 

중간에 9099099909999099999인가 하는 값이 이스터에그로 적혀있다. (잘 기억 안 남)

 

데이터 5

개노답 데이터다. 각 문장을 번역해보면 "x월 x일은 x년의 x번째 날입니다." 라는 문장이 나온다. 단어별로 일일이 번역해서 잘 조합하면 풀 수 있다.

 

중간에 4월 1일과 6월 1일 이스터에그가 섞여있다.

 

데이터 6

이 데이터도 규칙이 자명하지 않다. 숫자부분은 n^4임을 알 수 있는데 문자열 부분은 규칙이 조금 어렵다.

a부터 k개의 연속한 알파벳이 정확히 한 번 쓰인 문자열을 유효한 문자열이라 하자. (예시로, a, cab, dabc는 유효한 문자열이고, ddbc, ea, b는 그렇지 않다.)

이 때, 문자열 규칙은 T[x] = (사전순으로 x번째에 오는 유효한 문자열) 이다.

 

중간에 T[10000000000000000]="9099099909999099999" 라는 이스터에그가 있다.

 

데이터 7

앞부분 숫자들을 읽어보면, 1, 2, 11, 22, 121, 2101, ... 이다. 규칙을 찾아보면 2^k을 3진법 전개한 후, 역순으로 적은 것이다. k가 170얼마 정도까지 커지기 때문에 큰 수 연산으로 계산 후 출력해야 한다.

뒷부분에 2의 거듭제곱이 끝나고 0.xxxxxx형태의 숫자가 나오는데 이 부분은 규칙을 못 찾아서 따로 저장해놓고 그냥 출력했다. (데이터 8에서 설명하는 방식으로 압축해서 저장했다.)

 

소수점 파트에 이스터에그로 9099099909999099999가 숨어있다.

 

데이터 8

개인적으로 제일 어려웠던 데이터였다. 다른 사람들과 같이 고민해서 푼 데이터다. (풀이 아이디어를 제공해주신 quickn님, benedict0724님 감사합니다.) 

이미지로 변환해보면 곡선이 1개 나오는데 곡선의 시작지점을 저장하고, 이동방향을 저장해서 풀 수 있다.

#에서 #으로 이동할 때, x좌표와 y좌표의 절댓값이 1이하임을 확인할 수 있고, 이를 이용하면 이동방향을 0~7 중의 숫자 1개로 표현할 수 있다. 2번의 이동은 64가지이고, 알파벳과 숫자, 특수문자들을 다 모아보면 대략 80~90가지의 문자가 된다. 즉, 2번의 이동을 코드 1바이트에 저장하는 것이 가능하고, 이를 저장하면 대략 15KB가 된다.

 

이 데이터는 이스터에그가 없다.

 

데이터 9

1003*1003 바탕에 직선 여러개를 저장해놓은 데이터다.

직선의 기울기는 1, -1, 0, 무한대 총 4가지이고, 시작지점으로 가능한 점은 1003^2, 길이는 최대 1003이므로, 직선 1개에 대한 정보를 4*1003^3이하의 숫자 1개로 표현할 수 있다. 이는 대략 85^5보다 작은 값이므로, 알파벳과 숫자, 특수문자를 이용해서 5개의 문자로 저장할 수 있다.

데이터를 분석해보면 직선의 개수가 생각보다 적어서 코드 길이를 많이 차지하지는 않는다.

 

이 데이터는 이스터에그가 없다.

 

데이터 10

꽤 빡센 데이터다. 규칙이 데이터에 적혀있어서 엄청 어려운 수준은 아니다.

첫번째 부분에 있는 a_i의 규칙은 a_{i-1}과 a_{i-2}를 순서대로 붙여놓는 규칙이다.

두번째 부분에 있는 행렬 A_i의 원소들을 가로로 윗줄부터 읽어보면 a_i와 같다는 것을 확인할 수 있다.

이제 B_i만 구하면 풀 수 있는데 규칙이 A_i^n=B_i (mod 2)라고 적혀있는 것을 확인할 수 있다.

여기서 n이 어떤 숫자인지 알아야 하는데 이스터에그로 자주 등장한 9099099909999099999를 대입해서 계산해보면 실제로 성립한다.

 

시간복잡도는 O(N^4log9099099909999099999) (N=70)인데 백준에서는 0.5초에 돌아서 걱정하지 않아도 된다. (내 컴은 6초 걸림 ㅋㅋ)