백준 1780 : 종이의 개수 (파이썬)

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

1780번: 종이의 개수

---

코드 1

#https://teching.tistory.com/
import sys

cnt = {
    -1: 0,
    0: 0,
    1: 0
}


def check(paper, n):
    if n == 1:
        return True
    plag = paper[0][0]
    for i in range(n):
        for j in range(n):
            if plag != paper[i][j]:
                return False
    return True


def paper_split(paper, n):
    if check(paper, n):
        cnt[paper[0][0]] += 1
        return
    splitPaper = [
        [], [], [],
        [], [], [],
        [], [], []
    ]
    for i in range(n):
        if i < n // 3:
            splitPaper[0].append(paper[i][:n // 3])
            splitPaper[1].append(paper[i][n // 3:n * 2 // 3])
            splitPaper[2].append(paper[i][n * 2 // 3:])
        elif n // 3 <= i and i < n * 2 // 3:
            splitPaper[3].append(paper[i][:n // 3])
            splitPaper[4].append(paper[i][n // 3:n * 2 // 3])
            splitPaper[5].append(paper[i][n * 2 // 3:])
        else:
            splitPaper[6].append(paper[i][:n // 3])
            splitPaper[7].append(paper[i][n // 3:n * 2 // 3])
            splitPaper[8].append(paper[i][n * 2 // 3:])
    for p in splitPaper:
        paper_split(p, n // 3)


n = int(sys.stdin.readline().rstrip())
inPaper = []
for _ in range(n):
    inPaper.append(list(map(int, sys.stdin.readline().split())))
paper_split(inPaper, n)
for key in cnt:
    print(cnt[key])

해설

https://teching.tistory.com/116

백준 2630: 색종이 만들기 (파이썬)

 

https://teching.tistory.com/117

백준 1992: 쿼드트리 (파이썬)

이전 단계 문제들과 동일한 방법으로 구현을 했는데 시간이 엄청 오래 걸리고 메모리도 많이 먹었다.

기본적으로 입력도 많아지는데 배열을 계속 새로 만들고 list.append 연산을 많이 사용하기 때문으로 보였다.

따라서 해당 연산을 하지 않고 단순 좌표 계산을 하는 방법을 사용해서 새롭게 코드를 짜보았다.

코드 2

#https://teching.tistory.com/
import sys

cnt = {
    -1: 0,
    0: 0,
    1: 0
}


def check(x, y, n, paper):
    if n == 1:
        return True
    plag = paper[y][x]
    for i in range(y, y + n):
        for j in range(x, x + n):
            if plag != paper[i][j]:
                return False
    return True


def paper_split(x, y, n, paper):
    if check(x, y, n, paper):
        cnt[paper[y][x]] += 1
        return
    n //= 3
    for _ in range(3):
        paper_split(x, y, n, paper)
        paper_split(x + n, y, n, paper)
        paper_split(x + n*2, y, n, paper)
        y += n


n = int(sys.stdin.readline().rstrip())
inPaper = []
for _ in range(n):
    inPaper.append(list(map(int, sys.stdin.readline().split())))
paper_split(0, 0, n, inPaper)
for key in cnt:
    print(cnt[key])

 

결과

위 결과가 코드 2 결과고 아래 결과가  코드 1 결과인데  확실히 빠르고 메모리도 적게 차지한다.