백준 | 2630 - 색종이 만들기

📃 색종이 만들기

4등분하는 분할정복 문제

 

 

---

✏️ 문제

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

 

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

 

 

---

💡 해결방법

4등분 한 후 좌표를 어떻게 해야할 지 몰라서 굉장히 오랫동안 붙잡고 있던 문제 ^-^..

이 문제도 짱친이 도와줘서 좌표 겨우 이해했다. 😉 감사합니당

 

분할정복의 대표적으로 4등분을 하는 문제이다.

 

기본적인 흐름은 다음과 같다.

배열을 전체적으로 돌면서 만약 1인 수를 발견하면 cnt를 1씩 증가시킨다.

배열을 모두 돌았을 때 cnt가 0이면 배열에 있는 수가 모두 0이므로 white를 증가시키고, cnt가 n의 제곱이라면 배열에 있는 수가 모두 1이므로 blue를 증가시킨다.

만약 위 두 경우에 모두 속하지 않는다면 4등분으로 분할을 해야한다. -> 재귀함수를 호출한다.

 

가장 헷갈렸던 부분은 함수에 어떤 인수를 주어서 4등분을 해야할지 헷갈렸다. 처음에 아무 생각 없이 0이라고 명시한 수를 인수에 넣기도 했었는데... 이러면 중간에 다 꼬여서 돌아간다.

4등분한 배열의 각각 첫번째 좌표는 다음과 같이 생각하면 된다.

 

전체 배열의 길이가 n이므로 r,c는 시작점으로 인자를 넣어주니까 각각 r과 c 에 n//2씩 더해주면 위와 같은 좌표가 완성된다 !

완벽하게 이해해서 이제 헷갈일일 없다!

 

 

+) 다른 문제를 풀다가 ..

1을 발견했을 때 cnt를 올려주는 식으로 처리했는데 이보다 더 빠를 것 같은 방법을 하나 생각했다.

많은 분들이 이렇게 푼 것 같은데! target 숫자 하나를 정해두고 같지 않다면 중간에 빠져나올 수 있으므로 ..? 한번 해봐야겠다.

 

 

👩🏻‍💻 소스코드

# 2630 : 색종이 만들기

import sys

n = int(sys.stdin.readline())
d = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
blue = 0
white = 0


def paper(n, r, c):
    global blue
    global white
    cnt = 0
    for i in range(r, r+n):
        for j in range(c, c+n):
            if d[i][j] == 1:
                cnt += 1
    if cnt == 0:
        white += 1
    elif cnt == (n**2):
        blue += 1
    else:
        # for x in range(2):
        #     for y in range(2):
        #         paper(n//2, r+(n//2*x), c+(n//2*y))
        paper(n//2, r, c)
        paper(n//2, r+n//2, c)
        paper(n//2, r, c+n//2)
        paper(n//2, r+n//2, c+n//2)


paper(n, 0, 0)
print(white)
print(blue)

---

 

 

2630번: 색종이 만들기