프렉탈 평면은 다음과 같이 커진다. 시간 0에서 프렉탈은 흰색 정사각형 하나이다. 단위 시간(1)이 진행될 때마다 N×N개의 크기가 동일한 단위 정사각형으로 나누어진다. 만약 나누어진 정사각형이 흰색이라면 가운데 K×K 정사각형이 검정색으로 채워진다. N과 K는 둘 다 홀수이거나, 둘 다 짝수이다.
예를 들어, N=3, K=1이라면, 시간 1에 3×3 정사각형이 된다. 가운데 정사각형은 검정색이고, 나머지는 흰색이 된다. 시간 2때 9×9 정사각형이 되고, 17개는 검정이고, 나머지는 흰색이다.
s, N, K, R1, R2, C1, C2가 주어질 때, 시간 s일 때, R1행 C1열부터 R2행 C2열까지의 모습을 출력하는 프로그램을 작성하시오.
첫째 줄에 문제의 정답을 출력한다. 첫째 줄에 R1행의 모습을 출력하고 이런 식으로 총 R2-R1+1개의 줄에 출력하면 된다. 각 행의 모습을 출력할 때, C1열부터 C2열까지 차례대로 흰색이면 숫자 '0' 검정이면 숫자 '1'을 출력한다. 숫자 사이에 공백을 넣으면 안 된다.
입력 예시
1 5 3 0 4 0 4
출력 예시
00000
01110
01110
01110
00000
풀이
분할 정복을 이용하기 딱 좋은 문제. 현재 깊이를 depth라 하였을 때, 구간의 크기 N' = N ** (depth-1)이 된다. 하나의 전체 맵은 N' x N'의 구간으로 나눌 수 있으며, 이 중 행렬 모두 [(N'-K') // 2, (N'+K') // 2)가 포함되는 구간은 전부 black, 나머지는 depth가 1 작은 프랙탈로 이루어진다.
이 프렉탈을 일단 모두 구하는 것은 메모리 초과를 야기했다..(아마 모든 경우를 전부 리스트로 저장해서 그런가보다. 다른 언어나 혹은 리스트가 아닌 문자열을 이용한다면 괜찮을지도) 따라서 본 풀이는 필요한 구간, 즉 [R1, R2]x[C1, C2]에서의 구간만을 가지고 풀이하였다. 각 소구간을 분할하여 먼저 구하고, 그 소구간을 대구간에 반영하는 식으로 설계해보자. 이 때 소구간과 대구간의 좌표 매칭에 유의하도록 하자.
풀이 코드
s, N, K, R1, R2, C1, C2 = map(int, input().split())
base = [[0]*N for _ in range(N)]
for i in range((N-K)//2, (N+K)//2) :
for j in range((N-K)//2, (N+K)//2) :
base[i][j] = 1
def div_and_con(depth) :
if depth == 0 :
return [[0]]
if depth == 1 :
return base
block = N**(depth-1)
result = [[1]*(N*block) for _ in range(N*block)]
tmp = div_and_con(depth-1)
for i in range(N) :
ib = i*block
for j in range(N) :
jb = j*block
if (N-K) // 2 <= i < (N+K) // 2 and (N-K) // 2 <= j < (N+K) // 2 :
continue
for _i in range(block) :
for _j in range(block) :
result[ib+_i][jb+_j] = tmp[_i][_j]
del tmp
return result
ans = div_and_con(s)
for _ans in ans[R1:R2+1] :
print(*_ans[C1:C2+1], sep='')
