[백준✨] 1780번 <종이의 개수> / Python 문제풀이

해답)

import sys
sys.setrecursionlimit(10**8)


def input():
    return sys.stdin.readline().rstrip()


N = int(input())
board = []
result = [0, 0, 0]

for _ in range(N):
    board.append(list(map(int, input().split())))

# 종이가 조건에 맞는지


def isEnd(board, s_r, s_c, length):
    v = board[s_r][s_c]
    for i in range(s_r, s_r + length):
        for j in range(s_c, s_c + length):
            if board[i][j] != v:
                return False
    return True

# 분할


def divide(s_r, s_c, length):
    v = board[s_r][s_c]
    if isEnd(board, s_r, s_c, length):
        result[v] += 1
        return
    d = length // 3
    for i in range(s_r, s_r + length, d):
        for j in range(s_c, s_c + length, d):
            divide(i, j, d)


divide(0, 0, N)

print(result[-1])
print(result[0])
print(result[1])

---

풀이)

N 의 범위가 그렇게 크지 않으므로 구현만 잘 하면 시간초과 날 일은 없다!

 

종이가 하나로 체워졌는지 확인하는 함수(isEnd)와 

종이를 분할해가는 함수(divide)로 나누었다.

 

종이가 하나로 체워졌다면 result 리스트의 값을 갱신해준다.

참고로 result[-1] 은 여기서는 result[2] 와 같다.

 

 

 

 

* 위 문제의 저작권은 백준(https://www.acmicpc.net/) 에 있습니다.