[실버 I] 1074번. Z

 문제 

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

1074번: Z

 사용 언어 

Python3

 풀이 과정 

우왕 이 문제는 생각보다 엄청 빨리 풀었다. 처음 문제를 읽고 나서는 이게... 무슨 그래프 탐색인가 싶었는데 다시 읽어보니 그냥 나눠 생각하면 쉽게 풀 수 있을 것 같은 느낌?! 바로 분할 정복을 사용하는 문제였다.

 

이 문제는 재귀로 풀든 분할정복으로 풀든 4등분이 핵심이기 때문에 나는 먼저 4등분에 초점을 맞추고 나눠진 구역이 1, 2, 3, 4분면이라고 생각했다. 그리고 나서 보면 한 사각형의 첫 번째 칸은 전체 사각형의 1/4 만큼 지나온 숫자가 되기 때문에 그 점을 이용했다.

대충 이런 느낌... 그래서 N부터 1까지 1씩 줄어드는 for문을 돌며 원하는 칸의 숫자를 찾아간다.

 

이렇게 생각한대로 구현했더니 바로 맞았습니다!!

 

 제출 답안 

from sys import stdin
input = stdin.readline

N, r, c = map(int, input().split())
answer = 0
for i in range(N, 0, -1):
    mid = 2 ** (i - 1)
    end = 2 ** i
    # 1사분면
    if 0 <= r < mid and 0 <= c < mid:
        continue
    # 2사분면
    elif 0 <= r < mid and mid <= c < end:
        answer += mid * mid
        c -= mid
    # 3사분면
    elif mid <= r < end and 0 <= c < mid:
        answer += mid * mid * 2
        r -= mid
    # 4사분면
    elif mid <= r < end and mid <= c < end:
        answer += mid * mid * 3
        r -= mid
        c -= mid
        
print(answer)

 

 다른 사람 코드 

1. 분할정복

import sys

def dc(x,y,n):
    global cnt
    if x>r or x+n <= r or y>c or y+n <= c:
        cnt += n**2
        return 
    
    if n > 2:
        n//=2
        dc(x,y,n)
        dc(x,y+n,n)
        dc(x+n,y,n)
        dc(x+n,y+n,n)
    else:
        if x==r and y==c:
            print(cnt)
        elif x==r and y+1==c:
            print(cnt+1)
        elif x+1==r and y==c:
            print(cnt+2)
        else:
            print(cnt+3)
        sys.exit()
        
n,r,c = map(int,input().split())
cnt = 0
dc(0,0,2**n)

➡ 메모리는 같았는데 시간면에서 16ms가 더 걸렸다. 아마도 재귀로 함수를 호출하기 때문이지 않을까 싶다..

 

출처 : https://my-coding-notes.tistory.com/411