[BOJ] 1074 Z

date

Jul 7, 2023

slug

boj-1074

author

status

Public

문제 링크

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

문제

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

문제풀이

그림 패턴을 분석하면

row의 경우 n-1번째 있는 값은 (n-1)/2의 값에서 만큼 떨어져 있는 값의 를 더한 값 인것을 알 수있다.

col의 경우 n-1번째 있는 값은 (n-1)/2의 값에서 만큼 떨어져 잇는 값의 를 더한 값 인것 을알 수 있다.

즉 주어진 row와 col를 이진수로 변환후 1에 해당하는 인덱스를 N으로 할 수 있다.

N을 주어진 row와 col에 적용시켜 모두 더해주면 된다.

파이썬 문제풀이 코드


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

r_list = []
c_list = []

total = 0
while(r):
    r_list.append(r % 2) 
    r = r // 2
    
while(c):
    c_list.append(c % 2)
    c = c // 2

for i in range(len(r_list)):
    if r_list[i] == 1:
        total += 2 * ( 4 ** i)
    
for i in range(len(c_list)):
    if c_list[i] == 1:
        total += 4 ** i
    
print(total)

시간복잡도

O(1)

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

예제 입력


2 3 1

예제 출력


3 7 7


10 511 511

알고리즘 분류

분할 정복

재귀