색종이 만들기 [66]

분할 정복

정의 : 문제를 나눌 수 없을 때 까지 나누어, 나눈 각각을 풀고 다시 합병하여 전체 문제의 답을 얻는 알고리즘

1. divide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다.
2. conquer : 나누어진 문제가 여전히 분할이 가능하면, 다시 divide. 그렇지 않으면 문제를 푼다.
3. combine : conquer한 문제들을 병합하여 원래 문제이 답을 얻는다.

색종이 만들기

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

• 입력

  8
  1 1 0 0 0 0 1 1
  1 1 0 0 0 0 1 1
  0 0 0 0 1 1 0 0
  0 0 0 0 1 1 0 0
  1 0 0 0 1 1 1 1
  0 1 0 0 1 1 1 1
  0 0 1 1 1 1 1 1
  0 0 1 1 1 1 1 1
  

• 출력

  9
  7
  

내 코드

def func(arr,result):
    cnt = 0
    for a in arr:
        cnt += a.count(0)
        # print(a.count(1))
    # print(arr,cnt,len(arr))
    if len(arr)*len(arr) == cnt:
        # 모두 0
        result[0] +=1
        return result
    elif cnt ==0:
        #모두 1
        result[1] +=1
        return result
    else:
        m= len(arr) // 2
        # [row[j:j + m] for row in field[i:i + n]]
        arr1 = [row[0:m] for row in arr[0:m]]
        arr2 = [row[m:len(arr)] for row in arr[0:m]]
        arr3 = [row[0:m] for row in arr[m:len(arr)]]
        arr4 = [row[m:len(arr)] for row in arr[m:len(arr)]]
        result = func(arr1,result)
        result=func(arr2,result)
        result=func(arr3,result)
        result = func(arr4,result)
        return result


if __name__ == '__main__':
    n = int(input())
    input_arr = []


    for _ in range(n):
        input_arr.append(list(map(int, input().split(" "))))
    result = func(input_arr,[0,0]);
    print(result[0])
    print(result[1])