[백준/Python] 1074번 : Z

문제 정보

제목 : Z

번호 : 1074번

사용 언어 : Python

문제 링크

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

1074번: Z

 

시간 제한	메모리 제한
0.5 초 (추가 시간 없음)	512 MB

 

문제

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

 

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

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

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

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

 

입력

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

 

출력

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

 

입출력 예제

 

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2^N

---

나의 풀이

어려웠던 문제였습니다. 분할 정복, 재귀에 대해서 더 공부해야겠습니다. 여러 블로그를 참고하여 공부 및 이해하는 방향으로 문제를 해결했습니다.

N, r, c의 입력값을 받아 문자열을 나누어 정수형으로 변환 후 각각 저장합니다. visit에는 0을 저장합니다.

N이 0이 아닐동안 반복하는 while문을 생성하여 N을 1 감소시킨 후에 size에 2^N값을 저장합니다. 그 다음 size를 기준으로 해당 행(r)과 열(c)의 구역을 구할 것입니다.  if elif문을 이용하여 visit에 구역에 맞는 값을 저장하고 r과 c를 size만큼 감소시킵니다. 반복이 끝나면 visit를 출력합니다.

 

 

코드

import sys
input = sys.stdin.readline

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

visit = 0
while N != 0 :
    N -= 1
    size = 2 ** N

    # 제1사분면
    if r < size and c >= size :
        visit += size * size
        c -= size
    
    # 제2사분면
    elif r < size and c < size :
        pass

    # 제3사분면
    elif r >= size and c < size :
        visit += size * size * 2
        r -= size
    
    # 제4사분면
    elif r >= size and c >= size :
        visit += size * size * 3
        r -= size
        c -= size

print(visit)