백준 1074번 - Z(★★ / ▲ / 1) : Python

개요

• 풀이 시간 : 30~40분
• 시간 제한 : 0.5초
• 메모리 제한 : 512 MB
• 기출 : 백준 1074번
• 링크 : https://www.acmicpc.net/problem/1074

문제

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

만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 $2^{N-1} × 2^{N-1}$로 4등분 한 후에 재귀적으로 순서대로 방문한다.

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

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

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

입력

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

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

출력

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

해결방법

문제 이해하기

상당히 짜증나는 문제다. 규칙성은 보이는데 막상 r, c가 주어졌을때 해당 숫자를 찾기란 어렵다. 그리고 이 문제, 이전에 한번 풀려다가 때려친 문제이다...ㅋㅋㅋ

이번에도 좀 오래걸리긴 했는데(약 1시간) 결국 내 힘으로 풀긴 풀었다. 아래는 내가 고민한 흔적임...

알고리즘

내가 생각한 방법은 이렇다.

1. 현재 행렬 형태 중에 4등분했을때 r, c는 몇번째일지 구해본다.
2. 그렇게 몇번째인지 구한 다음에, r과 c, 시작점(num)을 업데이트 해준다. n을 1 빼준다.
3. 1과 2를 반복하면서 n이 1이 될때까지 반복한다.
4. r, c를 이용해서 최종적으로 구하면 끝

✅ 핵심은 4등분씩 계속 순차적으로 들어가는 것이다.

Python

내 코드

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

num = 0

while n > 1:
    # 4등분 중 몇번째인가
    ran = 2 ** (n - 1)
    if r >= ran:
        if c >= ran: # 4번째
            num += (4 ** (n - 1)) * 3
            r -= ran
            c -= ran
        else: # 3번째
            num += (4 ** (n - 1)) * 2
            r -= ran
            
    else:
        if c >= ran: # 2번째
            num += (4 ** (n - 1)) * 1
            c -= ran
        else: # 1번째
            pass
    
    # print(num, r, c)
    n -= 1

if r == 0:
    if c == 0:
        print(num)
    else:
        print(num + 1)
else:
    if c == 0:
        print(num + 2)
    else:
        print(num + 3)

5달전에는 못풀었다면 지금을 풀 수 있다구~~~👍👍