[백준, 분할정복/재귀] 1074_Z

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

1074번: Z

 

고민을 했지만 결국 해결책을 얻지 못했다.

처음 풀어볼 때, 재귀쪽으로 2 X 2까지 나누어진 뒤에 무언가 진행되어야한다라는 방식으로 고민했지만 항상 재귀와 관련한 문제만 만나면 블루스크린 뜨는 것 마냥 머리가 돌아가다 만다...

 

이 문제도 다른 분의 해결책을 참고해서 풀었다.

 

2가지 방법으로 풀 수 있었다.

1. 분할정복

2. 재귀

 

 

분할정복

• N X N 배열을 4개의 사분면으로 나눠서 생각하는 방법
  • 8 X 8 배열에서 목표 좌표 (a, b)를 (7,7)이라 가정하자
  • 첫 번째로 쪼갤 때(N = 3)
    • row : 7 >= 2 ^ 2
    • column : 7 >=  2 ^ 2
    • 둘다 N X N의 절반보다 크기떄문에 4사분면에 위치한다는 것을 알 수 있다.
    • 이때, 각 사분면의 시작값? 횟수는 이와 같다.
      • 각 사분면의 갯수는 (N / 2) X (N / 2), 즉 4 *4 = 16 이다.
      • 1 사분면 : 0 
      • 2 사분면 : 16
      • 3 사분면 : 32
      • 4 사분면 : 48
  • 이러한 방식으로 2 X 2 까지 쪼갠 뒤 계산하면 구할 수 있다.

import sys
input = sys.stdin.readline

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

ans = 0
while N != 0:
	N -= 1
	# 1사분면
	if r < 2 ** N and c < 2 ** N:
		ans += ( 2 ** N ) * ( 2 ** N ) * 0

	# 2사분면
	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)

 

 

재귀

2 * 2 배열 기준, (r, c) 가 2배가 됨에 따라 해당 위치의 방문값은 4배가 된다.

 

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

 

• 2 * (r % 2) + (c % 2) : 0, 1, 2, 3 을 더해주는 용도
• 4*sol(N-1, int(r/2), int(c/2)) : 좌표값을 2배씩 나눴을 때, 당시의 결과값을 구하기 위한 재귀함수
  • x,y 값이 2배씩 증감되면 결과값이 4배 증감하는 법칙을 사용한 것

이해하는데 조금 어려웠지만 정말 이게 재귀구나 라는 걸 느낄 수 있었다.

진짜 유연하게 재귀함수를 구현하는 게 신기하고 DP나 재귀를 계속 연습해야겠다.

 

import sys
input = sys.stdin.readline

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))
	
    
    # 4*sol(N-1, int(r/2), int(c/2))
    
    
print(sol(N, r, c))

 

 

 

해설 출처 : https://ggasoon2.tistory.com/11