BOJ 1780 - 종이의 개수

folder_open Algorithm / BOJ / silver | date_range 18 Nov 2024

sell #BOJ #1780 #silver #python #파이썬 #코딩테스트 #알고리즘

맨 위로

• 문제 링크
• 구현
• 코드

문제 링크

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

구현

재귀 문제이다. 각 재귀마다 사각형을 잘라 검사를 하면 된다. 검사를 해서 실패하면, 그 다음 재귀(즉, 사각형을 더 작게 자른다)로 들어가면 된다.

코드

from sys import stdin
input = lambda : stdin.readline()

count = dict()
count[0] = 0
count[-1] = 0
count[1] = 0

def check(n, paper, curr, tocheck):
    for i in range(n):
        for j in range(n):
            new_y, new_x = curr[0] + i, curr[1] + j
            if paper[new_y][new_x] != tocheck:
                return False
    return True

def recur(n, paper, curr) -> None:
    global count
    for i in range(0, n, n // 3):
        for j in range(0, n, n // 3):
            new_y, new_x = curr[0] + i, curr[1] + j
            if check(n // 3, paper, (new_y, new_x), paper[new_y][new_x]):
                count[paper[new_y][new_x]] += 1
            else:
                recur(n // 3, paper, (new_y, new_x))

if __name__ == '__main__':
    n = int(input())
    paper = []
    for _ in range(n):
        paper.append(list(map(int, input().split())))
    if check(n, paper, (0, 0), paper[0][0]):
        count[paper[0][0]] += 1
    else:
        recur(n, paper, (0, 0))
    print(count[-1])
    print(count[0])
    print(count[1])