1074 - Z

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

1074번: Z

 

 

- 분할 정복법

 

import sys
input = sys.stdin.readline

n, r, c = map(int, input().split())
pow2 = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768]
pow4 = [i*i for i in pow2]

area_list = list()
while n > 0:    # n번 반복
    if 0 <= r < pow2[n-1]:
        if 0 <= c < pow2[n-1]:
            area = 1
        else:
            area = 2
    else:
        if 0 <= c < pow2[n-1]:
            area = 3
        else:
            area = 4
    
    if area == 2:
        c -= pow2[n-1]
    elif area == 3:
        r -= pow2[n-1]
    elif area == 4:
        c -= pow2[n-1]
        r -= pow2[n-1]

    area_list.append(area)
    n -= 1

ans = 0
for i in range(len(area_list)):
    ans += pow4[i] * (area_list[-1-i]-1)

print(ans)

 

색종이 만들기에 이어서 이차원 리스트를 사용하는 분할 정복법 두 번째 문제를 해결했다

이상하게 이차원 리스트만 나오면 머리가 아파진다...

 

구역을 계속 쪼개가는 방식으로 구현했다

리스트를 건드리기 보다는 주어진 행과 열의 번호를 쪼개면서 계속 구역 1로 넘기는 연산을 진행해줬다

 

그래서 O(n)의 시간 복잡도로 구현할 수 있었다!

 

사실 처음에는 배열을 전부 구해서 그 값을 출력할까? 했는데 범위가 2*15인거보고 빠르게 마음 접었다

 

 

노트에 적고 코드로 구현해서 바로 맞아서 기부니가 좋다

이제 자러 갈거임