알고리즘 스터디 - 백준 1074번 : Z

문제 해석

• 크기가 2^N x 2^N인 2차원 배열을 Z모양으로 탐색
• N이 주어졌을때 r행 c열을 몇번째로 방문하는지 출력하는 프로그램 작성

어떤 알고리즘을 써야할까?

N=1

• 0, 1, 2, 3

N=2

• 0, 1, 2, 3 / 오른쪽 요소 2^2 * 1를 더함 4, 5, 6, 7

• 아래 요소 2^2 2를 더함 / 대각선 요소 2^2 3을 더함

• 2, 3, 1일 때 2^2 // 2보다 3이 크고 1이 작으니 3사분면에 존재

• 2^1의 요소의 (1, 1)에 2^2 * 2를 더함

• 열이 홀수면 +1, 열이 짝수면 +0

주어진 입력을 받는다.
1, 2, 3, 4분면으로 나눈다.
2사분면이면 열 -= 2^N
3사분면이면 행 -= 2^N
4사분면이면 행과 열 -= 2^N 둘다 진행

N, r, c = 3, 7, 7일 때

N -= 1
2^N = 4로 (7, 7) 체크 하면 4분면에 존재
7-4, 7-4 = 3, 3으로 변경
정답 += 2^2*2^2 * 3

N -= 1
2^N = 2로 (3, 3) 체크 하면 4분면에 존재
(1, 1)로 변경
정답 += 2^1*2^1 * 3

알고리즘 코드

• 혼자 고민하다가 원리는 알았는데 코딩으로 표현하는 것이 어려워 다른 사람 것들 중 가장 괜찮은 것을 가져왔다.

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

answer = 0

while N > 0:

	N -= 1

	if r < 2 ** N and c < 2 ** N:
		answer += ( 2 ** N ) * ( 2 ** N ) * 0

	elif r < 2 ** N and c >= 2 ** N: 
		answer += ( 2 ** N ) * ( 2 ** N ) * 1
		c -= ( 2 ** N )
         
	elif r >= 2 ** N and c < 2 ** N: 
		answer += ( 2 ** N ) * ( 2 ** N ) * 2
		r -= ( 2 ** N )
        
	else:
		answer += ( 2 ** N ) * ( 2 ** N ) * 3
		r -= ( 2 ** N )
		c -= ( 2 ** N )
    
print(answer)