1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서
www.acmicpc.net
일단 N이 2가 될때까지 쪼개야 한다.
이를 재귀로 표현하면 다음과 같다.
if N = 2:
else:
zet(N-1,r,c):
그리고 (r,c)가 몇 사분면에 있는지가 필요하다. ( Z방향으로 n사분면을 정한다.)
만약 첫 시도에서 (r,c)가 1사분면에 있지 않다면 바로 구할 수 있으나, 1사분면에 있다면 한번 더 쪼개줘야 한다.
def zet(N, x, y):
if x > N // 2:
i = 1
else:
i = 0
if c > N // 2:
j = 1
else:
j = 0
xy = [i, j]
for l in range(0,1):
for k in range(0,1):
if xy != [k, l]:
count += 1
else:
break
if xy != [k,l]:
break
그리고 1사분면에 있지 않을 때 방문 횟수를 구해보자.
일단 2 ^ (N-1) * 2 ^ (N-1) * (n사분면의 n -1)이 기본으로 들어가는 방문횟수이다.
그리고 해당 사분면에서 다시 한번 쪼개줘야 할 것이다.
또한, 쪼개지면서 각 좌표를 수정할 필요가 있다. (해당 위치에서 다시 사분면을 나누고 (x,y)가 쪼개진 Z안의 몇사분면이 있는지 알기위해서.)
else:
res = 2**(N)+n
if count == 0:
zet(N-1,x-N//2, y-N//2)
elif count == 1:
zet(N-1,x-N//2, y)
elif count == 2:
zet(N-1, x, y-N//2)
else count == 3:
zet(N-1, x, y-N//2)
이러면 N=2가 될때까지 쪼개질 것이다. N=2일 때, 해당 위치가 몇사분면에 있는지 알아보자.
if N == 2:
if x == 0 and y == 0:
num = 0
elif x == 1 and y == 0:
num = 1
elif x == 0 and y == 1:
num = 2
else:
num = 3
return numnum를 기반으로 방문 횟수를 구할 수 있으므로 식을 적어준다. 또한, 재귀함수를 실행함에 있어서 계속 넘겨줄 수 있도록 고안한다.
else:
res = 2**(N)*n
if count == 0:
return num + zet(N-1,x-N//2, y-N//2)
elif count == 1:
return num + zet(N-1,x-N//2, y)
elif count == 2:
return num + zet(N-1, x, y-N//2)
else:
return num + zet(N-1, x, y-N//2)이제 기본 플로우를 정해보자.
점이 몇 사분면에 있는지 판단하여, 기본 방문 횟수를 정한다. (Z방향으로 0, 1, 2, 3사분면을 정한다.)
2 ^ (N-1) * 2 ^ (N-1) * (n사분면의 n -1)
그리고 해당 사분면을 쪼개주고, 좌표를 수정한다.
일단 기본 코드는 하기와 같다. (물론 실행하니 답이 나오지 않았다.)
N, r, c = map(int,input().split())
def zet(N, x, y):
n=0
if N == 1:
if x == 0 and y == 0:
return 0
elif x == 1 and y == 0:
return 1
elif x == 0 and y == 1:
return 2
else:
return 3
else:
if x == N // 2 and y == N // 2:
n = 0
return 2**(N)*n + zet(N-1, x - N//2, y - N//2)
elif x == N // 2 and y == N // 2:
n = 1
return 2**(N)*n + zet(N-1, x - N//2, y)
elif x == N // 2 and y == N // 2:
n = 2
return 2**(N)*n + zet(N-1, x, y - N//2)
else:
n = 3
return 2**(N)*n + zet(N-1, x, y - N//2)
print(zet(N, r, c))2,3,1을 넣었더니 15가 나왔다.
무엇이 문제일까. 천천히 따라가보기로 한다.
N=2에 (3,1)이 된다.
3,1은 1사분면에 있으나, 파이썬에서 print에서 확인해보니 3사분면이 나왔다. 분류식이 잘못된 것이다.
생각해보니 등호가 아니라 부등호를 넣어줘야한다. 또한 한변의 길이가 2^n이므로 2로 나눠줄 필요가 없다.
(또 행열이 바뀌었다 ㅡ.ㅡ)
수정해보았다.
import sys
N, r, c = map(int,input().split())
def zet(N, x, y):
n=0
if N == 1:
if x == 0 and y == 0:
return 0
elif x == 1 and y == 0:
return 1
elif x == 0 and y == 1:
return 2
else:
return 3
else:
if x < N and y < N:
print("0사분면")
n = 0
return 2**(N)*n + zet(N-1, x - N//2, y - N//2)
elif x >= N and y < N:
print("1사분면")
n = 1
return 2**(N)*n + zet(N-1, x - N//2, y)
elif x < N and y >= N:
print("2사분면")
n = 2
return 2**(N)*n + zet(N-1, x, y - N//2)
else:
print("3사분면")
n = 3
return 2**(N)*n + zet(N-1, x, y - N//2)
print(zet(N, c, r))2,3,1의 경우 11은 제대로 나왔으나 3 7 7 은 제대로 나오지 않았다.
경로는 3사분면-3사분면-3사분면 들어간 것을 보니 제대로 들어갔다.
차근히 검산 해보니 여러곳에서 문제가 있었다. 수정은 다음과 같다.
import sys
N, r, c = map(int,input().split())
def zet(N, x, y):
n=0
if N == 1:
if x == 0 and y == 0:
#print("0사분면")
return 0
elif x == 1 and y == 0:
#print("1사분면")
return 1
elif x == 0 and y == 1:
#print("2사분면")
return 2
else:
#print("3사분면")
return 3
else:
if x < 2**(N-1) and y < 2**(N-1):
#print("0사분면")
n = 0
return 2**(N-1)*2**(N-1)*n + zet(N-1, x, y)
elif x >= 2**(N-1) and y < 2**(N-1):
#print("1사분면")
n = 1
return 2**(N-1)*2**(N-1)*n + zet(N-1, x - 2**(N-1), y)
elif x < 2**(N-1) and y >= 2**(N-1):
#print("2사분면")
n = 2
return 2**(N-1)*2**(N-1)*n + zet(N-1, x, y - 2**(N-1))
else:
#print("3사분면")
n = 3
return 2**(N-1)*2**(N-1)*n + zet(N-1, x - 2**(N-1), y - 2**(N-1))
print(zet(N, c, r))
심사 결과 패스했다.
댓글