[분할정복/DQ] 백준 1780 종이의 개수 - Python

 

[ Contents ]

• 1. 문제 (링크 참조)
• 2. 문제 풀이
• 3. 코드

 

 

1. 문제 (링크 참조)

1780번: 종이의 개수

 

 

 

2. 문제 풀이

 -1, 0, 1로만 이루어진 종이의 개수를 세는 문제입니다. 혼합되어 있으면, 9등분하여 다시 판별합니다.

 

2022.01.29 - [Algorithm] - [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘

[Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘

 분할정복 문제입니다. 먼저 종이가 한 가지 숫자로만 이루어져 있는지 판별하고, 섞여있으면 입력 범위를 9등분하여 재귀함수를 호출해야 합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

#입력
N = int(input())
paper = []
for _ in range(N):
    paper.append(list(map(int, input().split())))

minus = 0 # -1인 종이
zero = 0 # 0인 종이
plus = 0 # 1인 종이

# 같은 종이 판별기
# 모두 더했을 때 -n*n / n*n / 0만 나오면 같은 종이. 아니면 섞임
def isSamePaper(x, y, n):
    _sum = 0
    z = True
    for i in range(x, x+n):
        for j in range(y, y+n):
           _sum += paper[i][j]
           if paper[i][j] != 0: # 0이 아니면 False
                z = False

    if _sum == -1*n*n:
        return -1 # -1인 종이
    elif z == True:
        return 0 # 0인 종이
    elif _sum == n*n:
        return 1 # 1인 종이
    else:
        return 404 # 섞임

def searchPaper(a, b, n):
    x = isSamePaper(a, b, n)
    if x == 404: # 섞였을 경우, 9분할
        searchPaper(a, b, n//3) #(0,0)
        searchPaper(a + n//3, b, n//3) #(1,0)
        searchPaper(a + 2*(n//3), b, n//3) #(2,0)

        searchPaper(a, b+n//3, n//3) #(0,1)
        searchPaper(a, b+(n//3)*2, n//3) #(0,2)
        searchPaper(a+n//3, b+n//3, n//3) #(1,1)

        searchPaper(a+n//3, b+(n//3)*2, n//3) #(1,2)
        searchPaper(a+(n//3)*2, b+n//3, n//3) #(2,1)
        searchPaper(a+(n//3)*2, b+(n//3)*2, n//3) #(2,2)

    elif x == -1: #모두 -1
        global minus
        minus += 1
        # print("minus: ",minus, f"({a},{b}), {n}")
        return
    elif x == 0: #모두 0
        global zero
        zero += 1
        # print("zero: ",zero, f"({a},{b}), {n}")
        return
    else: #모두 1
        global plus
        plus += 1
        # print("plus: ",plus, f"({a},{b}), {n}")
        return

searchPaper(0, 0, N)
print(minus)
print(zero)
print(plus)

 

 입력범위를 모두 더해서 n*n이면 1, -n*n이면 -1, 0만 나왔으면 0으로 판별했습니다. 결과는 시간초과. 원래는 합이 0이면 0으로 판별했으나, 1과 -1이 동일한 개수로 있는 경우도 0으로 판별해서 코드가 복잡해졌습니다.

 

 

import sys
input = sys.stdin.readline

#입력
N = int(input())
paper = []
for _ in range(N):
    paper.append(list(map(int, input().split())))

minus = 0 # -1인 종이
zero = 0 # 0인 종이
plus = 0 # 1인 종이

# 같은 종이 판별기
def isSamePaper(x, y, n):
    for i in range(x, x+n):
        for j in range(y, y+n):
           if paper[i][j] != paper[x][y]: #맨 처음 수와 다른 수가 나오면 섞인 것
                return False
    return True #모두 같은 숫자로 이루어짐

# 분할 정복
def searchPaper(a, b, n):
    if not isSamePaper(a, b, n): # 섞였을 경우, 9분할
        searchPaper(a, b, n//3) #(0,0)
        searchPaper(a + n//3, b, n//3) #(1,0)
        searchPaper(a + 2*(n//3), b, n//3) #(2,0)

        searchPaper(a, b+n//3, n//3) #(0,1)
        searchPaper(a, b+(n//3)*2, n//3) #(0,2)
        searchPaper(a+n//3, b+n//3, n//3) #(1,1)

        searchPaper(a+n//3, b+(n//3)*2, n//3) #(1,2)
        searchPaper(a+(n//3)*2, b+n//3, n//3) #(2,1)
        searchPaper(a+(n//3)*2, b+(n//3)*2, n//3) #(2,2)

    else:
        if paper[a][b] == -1: #모두 -1
            global minus
            minus += 1
            # print("minus: ",minus, f"({a},{b}), {n}")
            return
        elif paper[a][b] == 0: #모두 0
            global zero
            zero += 1
            # print("zero: ",zero, f"({a},{b}), {n}")
            return
        else: #모두 1
            global plus
            plus += 1
            # print("plus: ",plus, f"({a},{b}), {n}")
            return

searchPaper(0, 0, N)
print(minus)
print(zero)
print(plus)

 맨 처음 수를 기준으로 잡고, 비교해서 다른 수가 나오는지 판별합니다. 이 방법은 모든 수를 비교하지 않고도, 다른 수가 나오면 바로 판별할 수 있는 장점이 있습니다.

 

 

    if not isSamePaper(a, b, n): # 섞였을 경우, 9분할
        for i in range(3):
            for j in range(3):
                searchPaper(a+(n//3)*i, b+(n//3)*j, n//3)

 위 코드에서는 풀어서 써서 조금 길어졌으나, 반복문을 이용하면 좀 더 간략하게 쓸 수 있습니다.