BOJ 1074번: Z

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

1074번: Z

전체 사각형을 네 개의 작은 사각형으로 계속 나누어나가면서 답을 더해가는 방법으로 풀었다.

각각의 작은 네 개의 작은 사각형을 Z 방향으로 0, 1, 2, 3 이라고 생각하고 위치에 따라 그 사각형 안의 개수에 곱해서 정답에 계속 더해준다.

이전에 한 번 풀었던 문제인데, 이전에 푼 방법이 시간이 조금 더 절약되더라.

import sys
input = sys.stdin.readline
N, r, c = map(int, input().split())
m = 2**(N-1)
square = 2**(2*N-2)
ans = 0

while(m>=1):
    i = r//m
    j = c//m
    if (i == 0):
        if (j == 0):
            k = 0
        else:
            k = 1
    else:
        if (j == 0):
            k = 2
        else:
            k = 3
    ans += square * k
    r = r % m
    c = c % m
    square = square//4
    m = m//2

print(ans)

이게 이번에 새롭게 풀었던 방법인데, 인덱스를 계속 나눠주면서 풀었고, m=(2**(N-1)) 을 매번 2로 나눠주면서 >=1인 경우 계속 반복했다.

 

n,r,c=map(int,input().split())
result=0
temp=2**n
while(temp>0):
    temp=temp//2
    if r<temp and c<temp: #1
        continue
    elif r<temp and c>=temp: #2
        result+=(temp)**2
        c-=temp
    elif r>=temp and c<temp: #3
        result+=(temp)**2*2
        r-=temp
    else: #4
        result+=(temp)**2*3
        r-=temp
        c-=temp
print(result)

이건 이전에 풀었던 방법, 코드도 짧고 훨씬 깔끔해보인다. 실제로 시간도 더 짧다. 아이디어는 동일하지만 구현 방법에서 차이가 있다.

나.. 좀 잘 풀었었네..? 근데 지금은 왜.......ㅎ