백준 1780번 <종이의 개수>

백준 알고리즘 1780번

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

1780번: 종이의 개수

---

1780번

N×N크기의 행렬로 표현되는 종이가 주어졌을 때, 아래와 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구하여라.

 

입력으로 첫 줄에 종이의 크기 N이 들어오고 그 다음 N개의 줄에 걸쳐 종이에 대한 정보가 들어온다.

 

출력으로 -1, 0, 1로 이루어진 종이의 개수를 출력하면 된다.

---

문제 해결

종이의 크기는 3의 승수꼴이다.

주어진 종이가 같은 숫자로 이루어져있는지 확인하고 같은 숫자로 이루어져있다면 해당 숫자의 count 값을 1 증가시키고 그렇지 않다면 종이를 9개로 자른다.

종이를 slicing 하는 것이 매우 중요하다. 파이썬에서 2차원 배열을 slicing 하는 것을 구현해야 하는데 너무 어려웠다.

 

• paper의 숫자가 같은 숫자로 이루어져있는지 확인한다.
  • 같은 숫자로 이루어져있으면 해당 숫자에 대해 count한다.
  • 같은 숫자로 이루어져있지 않으면 종이를 slicing 한다.
    • slicing한 종이에 대해 각각 answer 함수를 호출한다.

 

count한 값을 리스트에 저장했는데 종이를 이루는 숫자는 -1, 0, 1이기 때문에 각각을 index로 사용하면 된다.

그러면 [0으로 이루어진 종이의 개수, 1으로 이루어진 종이의 개수, -1으로 이루어진 종이의 개수]로 리스트에 저장된다.

---

코드

import sys
input = sys.stdin.readline
n = int(input())
paper = [list(map(int, input().split())) for _ in range(n)]

def same(n_, paper_):
    if n_ == 1:
        return True
    chk = paper_[0][0]
    for i in range(n_):
        for j in range(n_):
            if chk != paper_[i][j]:
                return False
    return True

def answer(n_, paper_):
    cnt = [0, 0, 0]
    if same(n_, paper_):
        cnt[paper_[0][0]] += 1
        return cnt
    tempN = n_ // 3
    for i in range(3):
        arr = paper_[i*tempN : (i+1)*tempN]
        for j in range(3):
            temp = [arr[k][j*tempN : (j+1) * tempN] for k in range(tempN)]
            recursion = answer(tempN, temp)
            cnt = [cnt[i] + recursion[i] for i in range(3)]
    return cnt
result = answer(n, paper)
print(result[-1])
print(result[0])
print(result[1])

---

결과

---