https://www.acmicpc.net/problem/1030
접근
s,N,K로 현재 전체 모양을 생각해볼 수 있고, R1~R2, C1~C2 그리드에 대한 값을 채워줘야한다.
다행히 R1~R2, C1~C2 구간의 길이가 최대 50이므로 각각의 포인트에 대해서 접근할 때 최악의 경우에도 2500번만 접근하면 된다.
R1~R2, C1~C2 사이의 임의의 점 r, c의 값은 0일까 1일까 정해야한다면,
s에 대해서 r,c의 좌표가 s-1일 때, s-2일 때, ... s=1일 때 어디로 부터 왔는가 생각하면 값을 찾을 수 있겠다 생각하였다.
예를 들어 보자.
웹사이트의 예제 3에서, 첫 값인 (r,c): (4,5)는 (r//N^s,c//N^s)으로 접근하면 s=3의 (0,0) 박스에서 s=2 박스의 (4,5) == (r%(N^s),c%(N^s))에 대응대고, s=2 에서는 (4,5)는 s=2의 박스의 중간에 있기 때문에 1임을 알 수 있다.
(4,7)은 s=2에서는 중앙에 없지만, s=1로 반복하였을 때 s=1 박스의 중간에 있게 되어 1임을 알 수 있다.
이런식으로 1임이 확인되면 반환해주고 s=0을 베이스라인으로 하여 탐색을 멈추게 코드를 짜면 될 것이라 생각하였다.
풀이
전체 코드입니다.
import sys; readline = sys.stdin.readline
s,N,K,r1,r2,c1,c2 = map(int,readline().split())
data = [[0]*(c2-c1+1) for _ in range(r2-r1+1)]
def query(r,c,s,x,y):
if s==0:
return None
if N**(s-1)*(N-K)//2 <= r < N**s - N**(s-1)*(N-K)//2 and N**(s-1)*(N-K)//2 <= c < N**s - N**(s-1)*(N-K)//2:
data[x-r1][y-c1] = 1
return None
else:
query(r%(N**(s-1)),c%(N**(s-1)),s-1,x,y)
for x in range(r1,r2+1):
for y in range(c1,c2+1):
query(x,y,s,x,y)
print('\n'.join(''.join(str(x) for x in y)for y in data))쿼리 함수의 첫번째 if는 베이스 라인으로 모든 s에 대해서 0임이 확인 되면 탐색을 끝낸다.
2번째 if 문이 1인지 아닌지 확인하는 작업으로 좌표가 만약 박스의 중간에 있으면 해당 좌표에 대응되는 출력되는 리스트에 1을 매칭하고 탐색을 끝낸다.
만약 중앙도 아니고 s가 아직 0에 도달 안했다면, s-1에 대응되는 좌표값을 전달인자로 다시 쿼리 함수를 호출한다.
코드는 간단해보이지만, 규칙을 생각해보느라 시간이 조금 걸렸습니다. 이와 같은 문제는 앞으로는 더 빠르게 풀 수 있을 것 같아요!
