[www.acmicpc.net/problem/2630]
#풀이- 분할 정복 문제이다. 분할 정복 문제는 보통 세 가지의 구성 요소가 있다.
- 작은 문제로 분할하는 과정(divid)
- 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)
- 더이상 답을 분할하지 않고 풀 수 있는 작은 문제(base case)
base case: 2차원 배열내부에 있는 배열의 길이가 2일때 4가지 원소를 비교해 알맞게 return 한다.
divid: 배열을 4가지로 바꿔서 재귀 시킨다.(l은 배열의 길이)
외쪽 위 : divid([[j for j in arr[i][:l//2]] for i in range(l//2)])
왼쪽 밑 : divid([[j for j in arr[i][:l//2]] for i in range(l//2,l)])
오른쪽 위: divid([[j for j in arr[i][l//2:]] for i in range(l//2)])
오른쪽 밑: divid([[j for j in arr[i][l//2:]] for i in range(l//2,l)])
merge: 파란색과 흰색을 각각 합쳐준다.
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 33 34 | import sys input = lambda : sys.stdin.readline().rstrip() n=int(input()) paper=[list(map(int,input().split())) for _ in range(n)] def divid(arr): l=len(arr[0]) #base case if l == 2: if arr[0][0] == arr[0][1] == arr[1][0]==arr[1][1]==0: return (1,0) elif arr[0][0] == arr[0][1] == arr[1][0]==arr[1][1]==1: return (0,1) else: s=arr[0][0] + arr[0][1] + arr[1][0]+arr[1][1] return (4-s,s) #divid elif type(arr[0]) == list: arr=[divid([[j for j in arr[i][:l//2]] for i in range(l//2)]),divid([[j for j in arr[i][:l//2]] for i in range(l//2,l)]),divid([[j for j in arr[i][l//2:]] for i in range(l//2)]),divid([[j for j in arr[i][l//2:]] for i in range(l//2,l)])] #merge if arr[0]==arr[1]==arr[2]==arr[3]==(1,0): return (1,0) elif arr[0]==arr[1]==arr[2]==arr[3]==(0,1): return (0,1) else: tmpx=tmpy=0 for x,y in arr: tmpx+=x tmpy+=y return(tmpx,tmpy) result=divid(paper) print("{}\n{}".format(result[0],result[1])) | cs |
댓글 쓰기