반응형
1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을
www.acmicpc.net
풀이
- 2^N * 2^N 쿠기의 배열을 Z모양으로 탐색한다.
- 한번에 정사각형 모양으로 탐색하므로 쪼갤 수 있는 가장 작은 단위까지 쪼개면서 세면된다.
- 4등분을 한 후 , 등분에 따라 0 , SIZE * 1/4 , SIZE * 2/4 , SIZE * 3/4 의 인덱스로 쪼개고 각각을 더해가면서 몇번째로 탐색하는지 알아낼 수 있다.
- 문제의 예제인 2 3 1 의 경우 , 처음 쪼갤때는 SIZE * 2/4 인 조각에 속하고 , 이후에는 0 , 1 , 2 , 3 중 3에 속하므로 SIZE * 2/4 ( 8 ) + 3 = 11 번째 탐색되는 경우이다.
import sys
n,r,c= map(int, sys.stdin.readline().split())
def check(r,c,n):
size = (2**n)**2
block = int(size/4)
ans = 0
move = 2**(n-1)
if n == 1:
if r==0 and c==0:
return 0
elif r==0 and c==1:
return 1
elif r==1 and c==0:
return 2
elif r==1 and c==1:
return 3
else:
if r<(2**(n-1)):
if c<(2**(n-1)):
ans += 0
ans += check(r,c,n-1)
else:
ans += block
ans += check(r,c-move,n-1)
else:
if c<(2**(n-1)):
ans += (2*block)
ans += check(r-move,c,n-1)
else:
ans += (3*block)
ans += check(r-move,c-move,n-1)
return ans
print(check(r,c,n))
반응형
'코딩 > 백준' 카테고리의 다른 글
알고리즘 - Python / 백준 - 1041번 : 주사위 (0) | 2021.09.08 |
---|---|
알고리즘 - Python / 백준 - 2023번 : 신기한 소수 (0) | 2021.09.07 |
알고리즘 - Python / 백준 - 1780번 : 종이의 개수 (0) | 2021.09.06 |
알고리즘 - Python / 백준 - 2116번 : 주사위 쌓기 (0) | 2021.09.04 |
알고리즘 - Python / 백준 - 1389번 : 케빈 베이컨의 6단계 법칙 (0) | 2021.08.31 |