[백준알고리즘] 1780번: 종이의 개수 -Python

[백준알고리즘] 1780번: 종이의 개수 -Python

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

1780번: 종이의 개수

추가) 이전에 풀었던 문제이지만 한 번 더 풀어봤다. 사실 쓴 코드 중에서 제일 깔끔한 거 같아서 내용을 조금 수정했다. 3번째 코드가 해당 코드다.

---

 

이전에 풀었던 쿼드 트리와 비슷하게 푸는 분할 정복 문제이다. 쿼드 트리에서 사용했던 코드를 이용해서 금방 끝내려고 했는데 생각보다 막혔다.

그리고 파이썬으로는 시간 초과가 잘 나는 것 같다. PyPy로도 통과한 코드가 많은 것을 보니..

 

 

여기서 세가지의 풀이를 볼 것이다.

1. 딕셔너리를 사용한 방법 - PyPy로만 통과했다.

2. 리스트를 사용하고 반환 값을 이용한 것이 아닌 직접 리스트에 접근해서 값을 수정 - Python으로도 통과했다.

3. 2번을 통과하고 제출된 코드들을 보다가 되게 깔끔한 코드를 발견해서 가져왔다. ㅎㅎ

3. 내가 새롭게 푼 코드다.

 

 

1.

딕셔너리에 키값으로 1, 0, -1을 주고 value값을 변경하는 방법으로 접근했다. 딕셔너리에서 같은 키를 합하는 방법도 찾았었는데, 개수가 3개밖에 안돼서 직접 일일이 넣어주었다.

같은 키로 합하는 방법은 링크로 걸어두겠다.

 

여기서는 처음에 Python으로 제출했을 때에는 시간 초과가 발생했었다. 2번과 비교해서 리스트와 딕셔너리의 차이일 수도 있지만 return 받고 처리하는 과정들도 2번에서는 없어져서 Python으로도 통과가 된 것 같다.

import sys

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

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


def count(start_x: int, start_y: int, n: int):
    temp = matrix[start_x][start_y]
    rtn = [0, 0, 0]
    for i in range(n):
        for j in range(n):
            if temp != matrix[start_x + i][start_y + j]:
                rtn = divide(start_x, start_y, n)
                return rtn

    rtn[temp + 1] += 1
    return rtn



def divide(start_x: int, start_y: int, n: int):
    result = [0, 0, 0]
    temp = []
    
    for i in range(3):
        for j in range(3):
            temp = count(start_x + i* n//3, start_y + j* n//3, n//3)
            result[0] += temp[0]; result[1] += temp[1]; result[2] += temp[2]

    return result


result = count(0, 0, N)
print(result[0])
print(result[1])
print(result[2])

 

 

2.

리스트를 사용하고 반환으로 값을 수정하지 않았다. 이 과정에서는 리스트에 각각 0, 1, 2번 index를 -1, 0, 1로 본 것이다.

딕셔너리에 비해서 바로 접근도 가능한 것도 속도에 영향이 있지 않았나 생각이 되기는 한다.

이 코드는 Python도 통과했다.

import sys

N = int(sys.stdin.readline())
matrix = []
result = [0] * 3

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


def check(start_x: int, start_y: int, n: int):
    temp = matrix[start_x][start_y]
    for i in range(n):
        for j in range(n):
            if temp != matrix[start_x + i][start_y + j]:
                return False

    return True



def divide(start_x: int, start_y: int, n: int):
    if check(start_x, start_y, n):
        result[matrix[start_x][start_y] + 1] += 1
    else:
        for i in range(3):
            for j in range(3):
                divide(start_x + i* n//3, start_y + j* n//3, n//3)
                
    return


divide(0, 0, N)
for i in range(3):
    print(result[i])

 

 

 

3. 

주어온 코드를 지우고 내가 새롭게 푼 코드다. 주어진 테이블이 모두 하나의 기준 (0, 0)의 값과 같지 않다면 총 9개로 구분되는 칸으로 나누어 9개의 서브 테이블을 만들도록 했다. 이러한 행위를 각 테이블이 모두 같은 수로 채워져 있을 때까지 반복을 했다. 

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def check(i, j, d):
    global paper
    pick = table[i][j]
    for it in range(i, i+d):
        for jt in range(j, j+d):
            if pick != table[it][jt]:
                newd = d//3
                for mi in range(0, 3):
                    for mj in range(0, 3):
                        check(i + mi*newd, j + mj*newd, newd)
                return

    paper[pick] += 1

n = int(input())
table = [list(map(int, input().split())) for _ in range(n)]
paper = [0, 0, 0]   # 0의 갯수, 1의 갯수, -1의 갯수
check(0, 0, n)
for i in range(-1, 2):
    print(paper[i])

 

 

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