[백준-파이썬] 🥈실버🥈 분할 정복 문제들

나는 특히 분할 정복이 어렵다..ㅠ 많이 풀어보지 않아서 그런 것 같다...
그래서 🥈실버🥈 분할 정복 문제를 몇 개 풀어봤다.

---

2630. 색종이 만들기

문제 보러 가기!
정사각형 형태로 종이가 주어진다. 칸마다 파랑일 수도 있고, 하양일 수도 있다.
주어진 범위의 모든 칸이 같은 색깔이면 그만 자른다. 색이 섞여 있으면 4등분을 한다. (세로로 반, 가로로 반. 정사각형 모양으로)

1. 파란 색 종이 개수를 저장하는 blue_cnt, 하얀 색 종이 개수를 저장하는 white_cnt를 0으로 초기화한다.
2. divide_and_conquer함수에 시작하는 인덱스와 끝나는 인덱스, 한 변의 길이를 넣는다.
3. divide_and_conquer 함수
   주어진 범위를 쭉~ 보면서(check 함수)
   1. 다 같은 색깔이면 하양인지 파랑인지 보고, 해당하는 종이 개수에 1을 더한다.
   2. 다른 색이 섞여 있으면 4등분을 해서 divide_and_conquer 함수에 넣는다.

import sys

input = sys.stdin.readline

N = int(input())
board = list(list(map(int, input().split())) for _ in range(N))
blue_cnt = 0
white_cnt = 0


def divide_and_conquer(start_i, start_j, end_i, end_j, size):
    global blue_cnt, white_cnt

    # 쭉 보기
    tmp = board[start_i][start_j]

    def check():
        for i in range(start_i, end_i):
            for j in range(start_j, end_j):
                if tmp != board[i][j]:
                    return False
        return True

    # 모두 같으면
    if check() == True:
        if tmp == 1:
            blue_cnt += 1
        elif tmp == 0:
            white_cnt += 1
    # 하나라도 다르면 4등분하기
    else:
        divide_and_conquer(start_i, start_j, start_i + size, start_j + size, size//2)
        divide_and_conquer(start_i, start_j + size, start_i + size, end_j, size//2)
        divide_and_conquer(start_i + size, start_j, end_i, start_j + size, size//2)
        divide_and_conquer(start_i + size, start_j + size, end_i, end_j, size//2)


divide_and_conquer(0, 0, N, N, N//2)
print(white_cnt)
print(blue_cnt)

문제를 풀 때는 끝나는 인덱스까지 넣어서 풀었는데, 그 부분은 필요하지 않다는 걸 나중에 알았다. size를 가지고 끝나는 인덱스를 쉽게 계산할 수 있기 때문이다.

---

1780. 종이의 개수

문제로 가기
위에 문제는 4등분이고, 이 문제는 9등분인 것만 다르다.

처음 풀이

처음에는 위 코드에서 4등분 부분을 9등분으로만 바꾸고, white_cnt와 blue_cnt 부분을 -1, 0, 1로만 바꿨다.
그랬더니 python으로는 시간 초과가 나왔고, pypy로 통과했다.

import sys

input = sys.stdin.readline

N = int(input())
board = list(list(map(int, input().split())) for _ in range(N))
one_cnt = 0
zero_cnt = 0
minus_one_cnt = 0


def divide_and_conquer(start_i, start_j, size):
    global one_cnt, zero_cnt, minus_one_cnt

    # 쭉 보기
    tmp = board[start_i][start_j]

    def check():
        for i in range(start_i, start_i + size):
            for j in range(start_j, start_j + size):
                if tmp != board[i][j]:
                    return False
        return True

    # 모두 같으면
    if check() == True:
        if tmp == 1:
            one_cnt += 1
        elif tmp == 0:
            zero_cnt += 1
        elif tmp == -1:
            minus_one_cnt += 1
    # 하나라도 다르면 9등분하기
    else:
        for i in range(3):
            for j in range(3):
                divide_and_conquer(start_i + ((size//3) * i), start_j + ((size//3) * j), size // 3)


divide_and_conquer(0, 0, N)
print(minus_one_cnt)
print(zero_cnt)
print(one_cnt)

두번째 풀이

python으로도 맞은 분이 많이 계셔서 그 코드들을 참고했다.
나는 숫자들이 모두 같을 때 -1인지, 1인지, 0인지 if로 판단하는 부분이 있었는데, 거기에서 시간이 걸리는 것 같았다.
그런데 어차피 숫자로 들어오니까!! 길이 3인 리스트를 만들고, 들어오는 숫자를 인덱스로 삼으면 if문이 필요 없었다.

def divide_and_conquer(start_i, start_j, size):
    global cnt

    # 쭉 보기
    tmp = board[start_i][start_j]

    def check():
        for i in range(start_i, start_i + size):
            for j in range(start_j, start_j + size):
                if tmp != board[i][j]:
                    return False
        return True

    # 모두 같으면
    if check() == True:
        cnt[tmp] += 1
    # 하나라도 다르면 9등분하기
    else:
        t = size // 3
        for i in range(3):
            for j in range(3):
                divide_and_conquer(start_i + (t * i), start_j + (t * j), t)


def main():
    divide_and_conquer(0, 0, N)
    print(cnt[-1])
    print(cnt[0])
    print(cnt[1])

if __name__ == '__main__':
    import sys

    input = sys.stdin.readline

    N = int(input())
    board = list(list(map(int, input().split())) for _ in range(N))
    cnt = [0]*3

    main()

그렇게 코드를 바꾸니 python으로도 통과할 수 있었다.

---

그밖에 푼 문제들

5904 Moo 게임 포스팅
4779 칸토어 집합 포스팅