[백준] 1074 - Z (풀이 : 파이썬)

문제 : https://www.acmicpc.net/problem/1074

1074번: Z

 

 

접근

---

1. 0부터 count해서 직접 세어가기 (brute force)

정답을 K라고 할 때, 1 ≤ N ≤ 15 조건에 의해 K는 최대 \({2^{15}} * {2^{15}}-1\)이다. 때문에 시간제한에 걸릴 것같다.

 

2. 행과 열 사이의 규칙 찾기 (분할 정복)

n=3 예제

2 X 2 => {0,1,2,3}

4 X 4  => { {0,1,2,3} , {4,5,6,7} , {8,9,10,11} , {12,13,14,15}}

16 X 16 .... 

 

 

 

 

$$0 * 2^{n}$$	$$1 * 2^{n}$$
$$2 * 2^{n}$$	$$3 * 2^{n}$$

z를 크게 네부분으로 나누어 점점 작게 쪼개가며 분할정복을 해가면 될 것 같다.

 

ex) n = 3 , r = 7 , c = 7

먼저 위의 테이블을 4분면으로 쪼개어 하나의 조각이 4 X 4 칸인 분면으로 나눈다.

이때 (7,7)은 4사분면에 해당된다. r = 4 + 2 + 1 , c = 4 + 2 + 1

 

이제 4분면만 보자 

다시 4분면을 2 X 2 칸인 분면으로 자르자. 이때 (7,7)은 4사분면에 해당한다.

r = 4 + 2 + 1 , c = 4 + 2 + 1

 

마지막으로 1 X 1 칸인 분면으로 잘라보면 (7,7)은 4사분면에 해당한다.

r = 4 + 2 + 1 , c = 4 + 2 + 1

 

이제 해당규칙을 찾아보자 Z로 쪼갤 수 있는 \({2^{n}} * {2^{n}}\)부터 2 X 2 까지 순서대로 각 사분면의 위치를 찾아가면 O(1)에 해결 가능하다.

 

또한 row , col 을 이진수로 변환하여 각 자리수 연산을 통해 4개의 사분면 중 어디에 있는지 판단이 가능하다

 

 

 

코드

---

N , r ,c = map(int,input().split())

mask = 0b1
num = 0
for _  in range(15):
    Rbit = r & mask
    Cbit = c & mask
    if Rbit == mask and Cbit == mask:
        num += mask * mask * 3 # 4사분면
    elif Rbit == mask and Cbit == 0:
        num += mask * mask * 2 # 3사분면
    elif Rbit == 0 and Cbit == mask:
        num += mask * mask # 1사분면
    # 2사분면에 해당하는 부분은 0
    mask = mask << 1 #다음 자리수로 넘어가기

print(num)