[백준알고리즘] 2630번: 색종이만들기 -Python

[백준알고리즘] 2630번: 색종이만들기 -Python

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

2630번: 색종이 만들기

 

학교 공부하느라 정신이 없다ㅏ..

머리 식힐 겸 간단한 거 하나 풀었다.

 

 

이 문제는 분할 정복 문제이다.

 

분할 정복과 동적 계획법은 비슷하지만 다른 개념이다. 간단하게 한 번 살펴보자면, 일단 둘 다 반복과 재귀를 이용하며 TOP-DOWN이나 BOTTOM-UP방식을 통해서 문제를 해결한다.

 

둘의 차이점은 동적 계획법은 작게 나눈 부분들을 해결해가면서 결과를 더 큰 부분을 푸는데 이용한다. 이때 분할되는 과정에서 작은 부분들이 중복되어서 여러 번 반복되어 나올 수 있기 때문에 Memoization도 같이 사용한다.

 

하지만 분할 정복도 문제를 풀 수 있는 가장 작은 단위의 문제로 만든 다음에 해결하고 병합(merge)하는 과정들을 한다. 하지만 이때 동적 계획법과는 달리 sub problems의 중복이 없다.

 

 

이 문제 또한 격자를 기준으로 나눈 부분 안에서 모두 같은 색인지 검사를 하기 때문에 중복되는 sub problems가 없게 된다.

 

 

처음에 n/2를 할 때 n이 홀수가 됐을 경우 처리를 어떻게 해주어야 하나 의문이 들었다. 처음에 10이 들어와서 sub problem의 길이가 5가 된다면 격자를 어떻게 나눠주어야 하는지 고민이 됐다. 2x2 1개, 2x3 2개, 3x3 1개가 어떻게 배치되느냐에 따라서 각 종이의 수가 달라질 것 같았기 때문이다.

 

하지만 일단 문제를 풀 때에는 문제에서 주어진 사진을 참고해서 풀었다.

보다시피 왼쪽 위 점에서부터 n/2 만큼씩 오른쪽과 아래로 되어있었기 때문에 I의 크기를 n/2 x n/2로 정하고 IV의 크기를 (n - n/2) x (n - n/2)로 정해서 풀었더니 맞았다고 나왔다.

 

중간에 반복문을 사용하기 귀찮아서 사이즈가 얼마 크지 않길래 재귀를 사용해서 풀었다.

count_one, count_zero는 전역 변수로 사용했는데 전역 변수는 함수 안에서 read는 가능하나 write이 불가능하기 때문에 global로 함수 안에서도 수정이 가능하게 해 주었다.

 

하지만 global은 되도록이면 사용하지 않는 것이 좋다. 매개변수와 반환을 이용해서 구성하는 것이 좋다.

 

import sys

N = int(sys.stdin.readline())
matrix = []

for i in range(N):
    matrix.append(list(map(int, sys.stdin.readline().strip().split())))

count_one = 0
count_zero = 0

def check(start_i, start_j, n):
    global count_one, count_zero
    type = matrix[start_i][start_j]
    flag = True
    
    for i in range(start_i, start_i + n):
        if not flag:
            break
        for j in range(start_j, start_j + n):
            if type != matrix[i][j]:
                flag = False
                check(start_i, start_j, n // 2)
                check(start_i, start_j + n // 2, n // 2)
                check(start_i + n // 2, start_j, n // 2)
                check(start_i + n // 2, start_j + n // 2, n // 2)
                break

    if flag:
        if type:
            count_one += 1
        else:
            count_zero += 1


check(0, 0, N)
print(count_zero)
print(count_one)

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다