[solved.ac 실버3] 2630_색종이 만들기

제한 사항

---

문제

아래 <그림 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로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

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

예제

---

나의 풀이

나는 이 문제를 DFS로 풀이했다.

깊이가 깊어질 때마다 1/4 크기의 색종이에 대해 검사했다.

def cut(arr, n):
    white = [[0]*n for _ in range(n)] # 0으로만 이루어진 흰색 색종이
    blue = [[1]*n for _ in range(n)] # 1로만 이루어진 파란 색종이
    if arr == white:
        # 흰색 색종이일때 처리
    elif arr == blue:
        # 파란 색종이일때 처리
    m = n//2 # 현재 크기의 절반
    paper = [
        [row[:m] for row in arr[:m]], # 왼쪽 위
        [row[m:] for row in arr[:m]], # 오른쪽 위
        [row[:m] for row in arr[m:]], # 왼쪽 아래
        [row[m:] for row in arr[m:]]  # 오른쪽 아래
    ]
    ...
    # cut(자른 종이, m) 호출하는 과정 필요
    # 적절한 처리 후
    # return 과정 필요

우선 cut이라는 함수에 들어오면 n 크기의 흰색 색종이와 파란 색종이를 만든다.

그리고 매개 변수로 입력 받은 arr가 흰색 /  파란 색종이인 경우 적절한 처리를 하고 return을 한다.

만약 흰색 / 파란 색종이라 아니라면 한번 더 4조각으로 잘라야 한다.

4조각으로 자르는 것은 위 코드를 참고하길 바란다.

---

이 문제에서 요구한 답은 흰색 색종이와 파란 색종이의 개수이다.

개수를 구하는 방법은 여러 가지가 있겠지만 나는 재미있는 방법을 생각해냈다.

def cut(arr, n):
    white = [[0]*n for _ in range(n)]
    blue = [[1]*n for _ in range(n)]
    if arr == white:
        return 100000
    elif arr == blue:
        return 1
    m = n//2
    paper = [
        [row[:m] for row in arr[:m]], # 왼쪽 위
        [row[m:] for row in arr[:m]], # 오른쪽 위
        [row[:m] for row in arr[m:]], # 왼쪽 아래
        [row[m:] for row in arr[m:]]  # 오른쪽 아래
    ]
    ...
    # cut(자른 종이, m) 호출하는 과정 필요
    # 적절한 처리 후
    # return 과정 필요

바로 white일 때는 100000을, blue일 때는 1을 return 했다.

우선 이해가 쉽도록 white일 때 10을, blue일 때 1을 return 한다고 했을 때 어떤 종이가 파란 색종이 3개와 하얀 색종이 1개로 이루어졌을 때 13이 return 된다.

13이라는 숫자에서 하얀 색종이 개수와 파란 색종이 개수를 구하고 싶다면 10으로 나눈 몫과 나머지를 구하면 된다.

하지만 조금 더 생각해보면 blue의 개수가 10개를 넘어가면 10의 자리로 넘어가게 되는데 이 때는 정확하게 구하기 어려워진다. 그래서 white일때 10이 아닌 충분히 큰 수를 return해야 한다.

만약 white가 100을 return했다면 13이 아닌 103이 return 되었을 것이다. 그러면 파란 색종이가 최대 99개일 때까지 구할 수 있다.

그렇다면 문제에서 blue 색종이의 최대 개수는 몇 개일까?

문제에 따르면 N은 2, 4, 8, 16, 32, 64, 128 중 하나라고 했다.

단순히 생각했을 때 최대로 많이 쪼개졌을 때는 n이 128일 때 128*128 = 16,384개이다.

실제로 가장 많은 경우는 [[0, 1], [1, 1]]과 같이 2x2 크기의 종이에 파란색이 3개 있는 것이 64 * 64개 있는 상황으로 64*64*3 = 12,288 개이다.

어찌됐든 10,000개를 넘어가기 때문에 나는 파란 색종이일 때 100,000을 return 하도록 설정했다. 

이제 cut 함수의 전체를 보면 다음과 같다.

def cut(arr, n):
    white = [[0]*n for _ in range(n)]
    blue = [[1]*n for _ in range(n)]
    if arr == white:
        return 100000
    elif arr == blue:
        return 1
    m = n//2
    paper = [
        [row[:m] for row in arr[:m]], # 왼쪽 위
        [row[m:] for row in arr[:m]], # 오른쪽 위
        [row[:m] for row in arr[m:]], # 왼쪽 아래
        [row[m:] for row in arr[m:]]  # 오른쪽 아래
    ]
    total = 0
    for p in paper:
        total += cut(p, m)
    return total

total에 숫자가 저장될 것이고, 이제 이 숫자를 100,000으로 나눈 몫과 나머지를 구하면 된다.

---

전체 코드

def cut(arr, n):
    white = [[0]*n for _ in range(n)]
    blue = [[1]*n for _ in range(n)]
    if arr == white:
        return 100000
    elif arr == blue:
        return 1
    m = n//2
    paper = [
        [row[:m] for row in arr[:m]], # 왼쪽 위
        [row[m:] for row in arr[:m]], # 오른쪽 위
        [row[:m] for row in arr[m:]], # 왼쪽 아래
        [row[m:] for row in arr[m:]]  # 오른쪽 아래
    ]
    total = 0
    for p in paper:
        total += cut(p, m)
    return total
    
n = int(input())
paper= []
for _ in range(n):
    paper.append(list(map(int, input().split())))

answer = cut(paper, n)
for i in divmod(answer, 100000):
    print(i)

참고로 divmod를 사용하면 몫과 나머지를 한 번에 구할 수 있다.

 

채점 결과