[Python] 백준 8481 - Generator

https://www.acmicpc.net/problem/8481

 

소요시간: 3일

풀이

이 문제를 왜 만들었을까?

아주 간@단한 문제이다! 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10이 주어지면 그에 걸맞는 출력만 하면 된다!!

 

0번 

#구현

ONTAK 2010를 출력하면 된다.

 

소요바이트: 19바이트

1번

#압축 #구현 #파싱

10개의 데이터들 중에서 길이가 가장 길다.

같은 알파벳이 반복되므로, G#2932#o#2931....과 같이 해당 문자와 등장 횟수를 미리 계산해서 문자열로 만든 후 출력하였다.

 

여담으로 반복을 줄인 원문은 해당 대회의 Godzilla라는 문제이다.

 

+ 반복되는 횟수가 계차수열이다. 숏코딩할 때 이용할 예정이다.

 

소요바이트: 13922바이트

2번

#구현

피보나치 수열을 일렬로 쭉 나열한 것이다. 그러나 어느 순간부터 길이가 안 길어진다. 어떠한 MOD로 나누어졌음을 예측할 수 있다.

계산해보면 해당 MOD는 9099099909999099999임을 알 수 있다.

 

마지막에 알 수 없는 0.

도 잘 출력해주자.

 

소요바이트: 168바이트

3번

#재귀 #구현

이스터에그 있음

어쩌면 이 문제들중에서 가장 유명한 문제라고 할 수 있겠다.

시에르핀스키 삼각형과 유사하게 생긴 거대 모양을 출력하는 문제인데, 크기는 1024*1024이다.

재귀함수를 이용하면 쉽게 출력할 수 있다.

 

중간 어딘가에 ONTAK 2010이라는 글자가 숨어있다.

이런 글자를 처리하기 위해 먼저 2차원 리스트에 전체 모양을 저장해놓고

나중에 따로 글자를 삽입하고

한꺼번에 출력하는 식으로 해결할 수 있다.

 

소요바이트: 1021바이트

4번

#소수 판정 #에라토스테네스의 체

이스터에그 있음

규칙은 다음과 같다.

2부터 400001까지 자연수중, 소수면 0, 합성수면 1이다.

이스터에그로 3333번째 줄에 9099099909999099999라는 수가 숨어있다.

 

소요바이트: 620바이트

5번

#폴란드어(?) #구현 #파싱

이스터에그 있음

폴란드어로 알 수 없는 말이 쭉 써져있다.

번역해보면

 

"1월 1일은 2000년의 1번째 날이다."

와 같은 문장이 2000/01/01부터 2020/12/31까지 적혀있다.

 

그런데 사실 잘 생각해보면

연도(2000-2020)에 대응하는 단어가 21개밖에 안되고

달이 12개, 날이 31개, 서수가 366개니까

그냥 알아서 잘 나눠서 저장한 다음 출력해주면 된다.

 

윤년을 조심하자.

 

이스터에그로 문장 어딘가에 어린이날과 만우절에 대한 설명이 있다.

 

소요바이트: 12547바이트

6번

#수학 #조합론 #문자열

이스터에그 있음

1부터 20000까지의 수에 대해 각각을 네제곱 한 것에 어떠한 문자열이 대응되어있다.

문자열 규칙은 다음과 같다.

 

a, ab, ba, abc, acb, bac, bca, cab, cba ....

 

즉, 초기 n개의 문자열을 사전순으로 배열한 것이다.

이 문자열은 팩토리얼 등으로 어떻게어떻게 잘 계산하면 빠르게 구할 수 있다.

 

이스터에그로 10000에서 9099099909999099999를 출력한다.

 

소요바이트: 803바이트

7번

#구현 #수학

이스터에그 있음

처음에 텍스트 편집기로 열고 도대체 뭐지 싶어서 깜짝 놀랐다.

축소해보니까 깨알같이 #으로 이루어진 문자가 보인다.

 

규칙은 2의 거듭제곱꼴 수를 3진법으로 바꾼 다음 거꾸로 한 것이다.

 

살짝 구현에 애먹었던 것이, 파일 크기가 가로로 1000이라

숫자를 적을 때 미리 그 길이를 계산해주고 1000을 넘어가면 다음 줄에 적어주어야 한다.

 

마지막에 의미불명의 소수점 아래 수들은 그냥 눈으로 보고 하드코딩했다.

이스터에그로 소수점 어딘가에 9099099909999099999가 있다.

 

소요바이트: 2864바이트

8번

#구현 #그래프 탐색 #그래프 이론 #압축

웬 나선을 그려야 하는 문제이다.

시작점은 (500, 500)인데, 다행스럽게도 다음 나선이 이어지는 곳은 그 주위 8칸 중에 하나이다.

그래서 그래프탐색해주며 방향을 0, 1, 2, 3, 4, 5, 6, 7에 대응해서 길이가 30000자정도 되는 수열을 얻었는데,

이 수열을 4자리씩 묶어서 아스키문자화 하면 길이를 확 줄일 수 있다.(바이트수는 절반정도밖에 안줄어드는듯ㅠㅠ)

 

소요바이트: 15834바이트

9번

#구현 #그래프 탐색 #그래프 이론 #압축

직선들이 마구잡이로 그려져있다.

방향은 가로, 세로, 대각선(2개) 해서 총 4개인데,

시작점들을 찾아준 이후 직선을 따라가면서 길이를 기록하고,

(시작점, 길이, 방향) 정보로 직선 1개를 표현할 수 있다.

 

소요바이트: 6807바이트

10번

#행렬 #문자열 #분할 정복을 이용한 거듭제곱 #비트마스킹

가장 어렵고 까다로웠던 문제이다.

난해한 출력 양식탓도 있는데,

행렬 부분이 Hell이다.

 

a_i는 단순히 피보나치 수열마냥 두 수열을 계속 이어주는 것인데

이 수열이 A_i에 대한 힌트이다.

a_i를 정사각형으로 순서대로 배열하면 그것이 A_i가 된다!

한 17번정도까지 구해보면 그 길이가 충분히 4900을 넘는데, 이를 이용해서 A_70까지 잘 구할 수 있다.

 

B_i는 A_i를 n번 거듭제곱해주는 것에다가 mod2를 하는 것이다. n이 무엇일까?

 

바로 9099099909999099999다.

 

그렇기 때문에 그냥 거듭제곱해서는 안되고, 다음 두 가지 스킬을 써야한다.

1. 분할 정복을 이용한 거듭제곱

2. mod2라 결과가 0, 1밖에 안되기때문에 다음과 같은 생각을 해볼 수 있다.

원래는 행렬 곱셈 연산이 $O(N^{3})$정도인데, 비트마스킹을 이용해서 행렬의 한 줄을 아예 한 수로 만들어버리고 곱셈과 비트 연산을 적절히 해버리면

$O(N^{3})$을 놀랍게도 $O(N^{2})$로 줄일 수 있다.

 

이 스킬로 충분히 빠른 시간 안에 실시간으로 행렬들을 계산할 수 있다.

 

소요바이트: 2146바이트