[www.acmicpc.net/problem/1074]
#풀이- 분할 정복 문제이다. 분할 정복 문제는 보통 세 가지의 구성 요소가 있다.
- 작은 문제로 분할하는 과정(divid)
- 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)
- 더이상 답을 분할하지 않고 풀 수 있는 작은 문제(base case)
1. 중앙을 기준으로 4사분면으로 나누어 해당 위치가 몇 사분면에 있는지 판단한다.(divid)
2. 해당 사분면 이전의 사분면들의 크기를 더해준다.(merge)
3. 더 이상 사분면으로 나누어 지지않으면 결과를 출력한다.(base case)
- 처음에 모든 경우를 배열에 담을려 했더니 메모리가 초과되었다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | import sys sys.setrecursionlimit(10**6) input = lambda : sys.stdin.readline().rstrip() n,x,y=map(int,input().split()) n=2**n count=0 #divid(x시작값,x끝값,y시작값,y끝값) def divid(s_x,e_x,s_y,e_y): global count size=(e_x-s_x)//2 if size==0: print(count) #어느 사분면에 있는지 판정 해당 사분면에 없으면 사분면의 크기를 더해준다 else: if s_x<=x<s_x+size and s_y<=y<s_y+size: divid(s_x,s_x+size,s_y,s_y+size) else: count+=size**2 if s_x<=x<s_x+size and s_y+size<= y < e_y: divid(s_x,s_x+size,s_y+size,e_y) else: count+=size**2 if s_x+size<=x<e_x and s_y<=y<s_y+size: divid(s_x+size,e_x,s_y,s_y+size) else: count+=size**2 if s_x+size<=x<e_x and s_y+size<=y<e_y: divid(s_x+size,e_x,s_y+size,e_y) divid(0,n,0,n) | cs |
댓글 쓰기