BOJ2630 색종이 만들기
문제
BOJ2630 색종이 만들기
실버III | 백준 2630 | Python3 파이썬 풀이
알고리즘
BOJ1780 종이의 개수문제와 매우 유사하다. (BOJ1780 종이의 개수 - 풀이)
이 문제는 문제에 설명이 아주 자세하게 쓰여있어서 그대로 따라 구현하면 된다.
이런 종이의 경우
위 사진과 같이 나누면 된다.
각 종이를 4등분 해나가며 그 그룹이 같은 값(1 또는 0)으로 이루어져있다면 더 이상 나누지 않아도 된다.
파이썬의 2차원 리스트 슬라이싱을 이용해 나눠진 4개의 정사각형 그룹으로 재귀함수를 호출한다.
check([row[:c//2] for row in part[:c//2]], c//2)
check([row[:c//2] for row in part[c//2:]], c//2)
check([row[c//2:] for row in part[:c//2]], c//2)
check([row[c//2:] for row in part[c//2:]], c//2)
코드
import sys
input = sys.stdin.readline
blue = 0 # 1 갸수
white = 0 # 0 개수
# 파란색(1)의 개수를 세는 함수
def count_blue(part, c):
count = 0
for i in range(c):
for j in range(c):
if part[i][j] == 1:
count += 1
return count
def check(part, c):
global blue, white
# 1x1 크기라면
if c == 1:
if part[0][0] == 1:
blue += 1
else:
white += 1
return
# 전부 파란색(1)이라면
if count_blue(part, c) == c * c:
blue += 1
return
# 전부 흰색(0)이라면
elif count_blue(part, c) == 0:
white += 1
return
# 정사각형 4개 그룹으로 나누어 재귀 호출
else:
check([row[:c//2] for row in part[:c//2]], c//2)
check([row[:c//2] for row in part[c//2:]], c//2)
check([row[c//2:] for row in part[:c//2]], c//2)
check([row[c//2:] for row in part[c//2:]], c//2)
N = int(input())
p = [list(map(int, input().split())) for _ in range(N)]
check(p, N)
print(white)
print(blue)
결과
Author And Source
이 문제에 관하여(BOJ2630 색종이 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehe228/boj2630저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)