[알고리즘][Python] 백준 1780 종이의 개수 문제 풀이

문제 출처 :www.acmicpc.net/problem/1780

1780번: 종이의 개수

---

문제 해석 : 자른 종이의 모든 수가 같은 경우를 -1, 0, 1 케이스로 카운팅하여 출력하는 문제이다. 만약 모든 수가 같지 않으면 다시 종이를 9등분하여 행위를 반복한다.

 

문제 풀이 :  전형적인 분할 정복 문제로 작은 문제로 부터 큰 문제로 생각하여 풀이를 진행하면 풀 수 있다. 

1. 종이의 모든 내용이 같은지 체크한다.

2. 같지 않다면 인덱싱을 통해서 재귀적으로 이를 수행한다.

3. global count를 출력한다.

 

가능한 다른 풀이 : 직접 행렬을 자르는 것 말고 인덱스를 통해서 파라미터로 문제를 풀이 할 수도 있을 것 같다.

 

---

풀이 코드

N = int(input())
count_1 = 0 # -1
count_2 = 0 # 0
count_3 = 0 # 1
arr = []

for _ in range(N):
    arr.append(list(map(int, input().split())))

def all(arr):

    length = len(arr)
    A = arr[0][0]
    for i in range(length):
        for j in range(length):
            if A != arr[i][j]:
                return False
    return True

def check(arr):
    global count_1
    global count_2
    global count_3

    if all(arr):
        if arr[0][0] == -1:
            count_1 += 1
            return True
        elif arr[0][0] == 0:
            count_2 += 1
            return True
        elif arr[0][0] == 1:
            count_3 += 1
            return True
    else:
        length = len(arr)//3
        temp = []
        for i in range(3):
            start = length * i
            end = length * (i + 1)

            for j in range(3):

                start_2 = length * j
                end_2 = length * (j+1)
                new_arr = arr[start:end]

                for element in new_arr:
                    temp.append(element[start_2:end_2])
                check(temp)
                temp = []

check(arr)
print(count_1)
print(count_2)
print(count_3)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.