백준 1074번 - Z ( python )

 

 

백준 1074번 Z 입니다.

 

문제를 보자면,

 

( 이미지 클릭하면 크게 볼 수 있음 )

 

 

 

배열의 크기는 가로 (2 ** N ) * 세로 (2 ** N) 이며,

그 배열안에는 위와 같은 z 모양의 규칙을 가지며 숫자가 들어갑니다.

 

 

 

 

 

그랬을때 (r,c) 좌표에 해당하는 숫자를 구하면 됩니다.

 

 

예제 입력2 ( 3, 7, 7 ) 예제를 볼게요.

 

 

 

N이 3일때 , 7행 7열의 값이 63인 모습. 

 

 

( 고민타임.. )

 

 

 

 

 

 

 

 

 

 

 

 

-----------------------------------------------------------

 

 

1074번 문제의 알고리즘 분류

 

 

문제 유형은 분할정복과 재귀라고 하네요

 

간단해 보이지만 상당히 어려웠습니다 ㅜ..

 

2의 n개만큼 배열을 만들고 숫자를 넣고 좌표에 해당하는 값을 찾으려고 했으나

조건으로 N 은 15 까지 가능하니깐 가로 2의 15승 * 세로 2의 15승 = 2의 30승.. 딱봐도 아니죠?

배열을 만드는것은 아닌것같습니다.

 

 

2가지 방법으로 풀이를 해보겠습니다. (분할, 재귀)

 

첫째로, 분할정복 측면으로 접근하자면, 계속 4개의 영역으로 나누는 규칙으로 분할할 수가 있습니다.

 

계속 어떤영역에 속해있나 분할해가며, 좌표에 해당하는 값의 규칙을 찾아가볼게요.

 

( N = 3, 7행 7열의 값은 63 )

 

 

첫번째  ( N = 3 )

 

이렇게 4개의 영역으로 계속 분할하며 어떤 규칙이 있나 알아볼게요

 

첫번째로 쪼갰을때 ( 7 , 7 ) 은 N = 3인 영역에서 제4 사분면에 해당합니다. 

( 코드로 접근하면 가로 좌표 7 >= 2의 2승 , 세로 좌표 7 >= 2의 2승 이므로 제4 사분면. )

 

그리고 제 4사분면은 48부터 시작하는 모습.

 

각 사분면의 개수는 16 ( 2의 2승 * 2의 2승 ) 이니까

 

제2 사분면은 0

제1 사분면은 16

제3 사분면은 32

제4 사분면은 48부터 시작하고 있어요

 

 

두번째. N = 2 라고 볼 수 있죠?

 

두번째로 쪼갰을땐 ( 7 , 7 ) 의 좌표는 ( 3 , 3 ) 이 됩니다.

( 가로세로가 네칸씩 줄어드니깐, 7 - 2의 2승 = 3.)

 

또한 ( 3 , 3 ) 은 N = 2인 영역에서 제4 사분면에 해당하는 모습.

( 3 >= 2의 1승 , 3 >= 2의 1승 이므로 )

 

48을 뺏다고 가정하면, 

제4 사분면은 12부터 시작합니다.

( 각 사분면의 개수가 2의 2승 으로 4 니깐 4 * 3 = 12. )

 

( N = 2, 3행 3열의 값은 63 - 48 = 12 )

 

 

 

 

세번째 N = 1

 

 

세번째로 쪼개면 ( 3 , 3 ) 의 좌표는 ( 1 , 1 ) 로, 제4 사분면에 해당합니다.

( 가로세로가 두칸씩 줄어드니깐, 3 - 2의1승 = 1 )

 

그리고 48을 빼고 12 를 또 뺏을때 

제 4사분면인 ( 1 , 1 )은 3인 모습

(각 영역의 개수는 2의 0승 으로 1 니깐 1 * 3  = 3.)

 

그래서 48 + 12 + 3 은 63이 됩니다.

 

( N = 1, 1행 1열의 값은 63 - 48 - 12 = 3 )

 

 

 

규칙이 조금 보이시나요?

 

 

 

코드로 보신다면 더 이해하시기 쉬울 수도 있을 것 같습니다.

 

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

ans = 0

while N != 0:

	N -= 1

	# 제2사분면
	if r < 2 ** N and c < 2 ** N:
		ans += ( 2 ** N ) * ( 2 ** N ) * 0

	# 제1사분면
	elif r < 2 ** N and c >= 2 ** N: 
		ans += ( 2 ** N ) * ( 2 ** N ) * 1
		c -= ( 2 ** N )
        
	# 제3사분면    
	elif r >= 2 ** N and c < 2 ** N: 
		ans += ( 2 ** N ) * ( 2 ** N ) * 2
		r -= ( 2 ** N )
        
	# 제4사분면    
	else:
		ans += ( 2 ** N ) * ( 2 ** N ) * 3
		r -= ( 2 ** N )
		c -= ( 2 ** N )
    
print(ans)

 

잘 작동하는 모습

 

 

 

이런식으로 4개의 영역으로 계속 분할하는 방식으로 접근해보았습니다.

 

 

 

 

이번엔 재귀로 접근해보겠습니다.

 

 

빨간선 Z를 다지우고 ( 빨간선 너무나 강렬.. )

 

자세히 보면

 

 

 

 

제일 작은 2*2 박스

 

0  1

2  3

로부터 각각 ( 0 제외 )

 

 

좌표r,c가 2배가 됨에 따라

값이 4의 배수로 확장하는 것을 볼 수 있습니다.

 

ex)  8 ( 2, 0 ) - > 32 ( 4, 0 )

ex) 14 ( 2, 3 ) - > 56 ( 4, 6 )

 

 

이 방식으로 재귀함수를 만들면,

 

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

def sol(N, r, c):

	if N == 0:
		return 0
        
	return 2*(r%2)+(c%2) + 4*sol(N-1, int(r/2), int(c/2))

print(sol(N, r, c))

 

이렇게도 풀 수 있습니다. 

 

2*(r%2)+(c%2)는 그림에서 화살표라고 보시면됩니다.

4의 배수인 값으로부터 네모칸에서 이동하는

( 12와 0 에도 보이지 않는 화살표가 존재하는 모습. )

 

 

4*sol( N-1, int(r/2), int(c/2) ) 는

이제 4의 배수하기 이전의 값이라고 볼 수 있죠..! ( 이전 값의 좌표가 r // 2, c // 2 )

 

N이 0이 될 때까지

 

정말 짧죠 역시 재귀입니다.

 

 

추가 예시로

44를 예로 들어볼게요. 44는 11에서 4를 곱한수입니다.

11은 8에서 3을 더한 값입니다. ( 2 * (1) + 1 = 3 )

8은 2에 4를 곱한수죠?

 

그래서  0 + 4 * ( 3 + 4 * ( 2 + 4 * ( 0 ) ) ) 는 44 가 나오는 모습.

 

 

코드만 보면 어려울 수도 있지만,

그림과 함께 보신다면 이해하시는데 도움이 될거라 생각합니다~

 

 

 

이렇게 재귀로도 풀어봤습니다.

 

 

감사합니다!!

 

 

 

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