BOJ1780 종이의 개수
문제
BOJ1780 종이의 개수
실버II | 백준 1780 | Python3 파이썬 풀이
알고리즘
BOJ2630 색종이 만들기 문제와 매우 유사하다. (BOJ2630 색종이 만들기 - 풀이) 색종이 만들기는 4등분하지만, 이 문제는 9등분한다.
- 종이를 9개의 정사각형 그룹으로 나눈 뒤, 각 그룹이 모두 같은 값이라면 그 종이는 쓸 수 있는 종이이므로 그 값에 따른 개수를 기록한다.
- 만약 종이의 크기가 1x1까지 왔다면 더 이상 자를 수 없으므로 그 종이의 값에 따른 개수를 기록한다.
Python의 리스트 슬라이싱을 이용해 2차원 배열을 9개의 정사각형 그룹으로 나누어 재귀 함수를 호출한다.
check([row[:c//3] for row in part[:c//3]], c//3)
check([row[:c//3] for row in part[c//3:c//3*2]], c//3)
check([row[:c//3] for row in part[c//3*2:]], c//3)
check([row[c//3:c//3*2] for row in part[:c//3]], c//3)
check([row[c//3:c//3*2] for row in part[c//3:c//3*2]], c//3)
check([row[c//3:c//3*2] for row in part[c//3*2:]], c//3)
check([row[c//3*2:] for row in part[:c//3]], c//3)
check([row[c//3*2:] for row in part[c//3:c//3*2]], c//3)
check([row[c//3*2:] for row in part[c//3*2:]], c//3)
2차원 배열의 경우는 위와 같이 for문을 이용해 행과 열을 각각 슬라이싱해야 한다.
코드
import sys
input = sys.stdin.readline
mone = 0 # -1 그룹 개수
zero = 0 # 0 그룹 개수
pone = 0 # +1 그룹 개수
# 해당 그룹의 특정 수의 개수를 카운트하는 함수
def count(part, c, x):
count = 0
for i in range(c):
for j in range(c):
if part[i][j] == x:
count += 1
return count
def check(part, c):
global pone, zero, mone
# 만약 블록이 1x1이라면 값에 따라 카운트 증가
if c == 1:
if part[0][0] == 1:
pone += 1
elif part[0][0] == 0:
zero += 1
else:
mone += 1
return
# 그 그룹의 칸이 전부 -1이라면
if count(part, c, -1) == c * c:
mone += 1
return
# 전부 0이라면
elif count(part, c, 0) == c * c:
zero += 1
return
# 전부 1이라면
elif count(part, c, 1) == c * c:
pone += 1
# 다른 값이 섞여 있다면 9개의 정사각형 그룹으로 분할해서 체크하기
else:
check([row[:c//3] for row in part[:c//3]], c//3)
check([row[:c//3] for row in part[c//3:c//3*2]], c//3)
check([row[:c//3] for row in part[c//3*2:]], c//3)
check([row[c//3:c//3*2] for row in part[:c//3]], c//3)
check([row[c//3:c//3*2] for row in part[c//3:c//3*2]], c//3)
check([row[c//3:c//3*2] for row in part[c//3*2:]], c//3)
check([row[c//3*2:] for row in part[:c//3]], c//3)
check([row[c//3*2:] for row in part[c//3:c//3*2]], c//3)
check([row[c//3*2:] for row in part[c//3*2:]], c//3)
N = int(input())
p = [list(map(int, input().split())) for _ in range(N)]
check(p, N)
# 각 값으로 이루어진 그룹의 개수 출력
print(mone)
print(zero)
print(pone)
결과
Python3로 제출하면 시간초과가 발생한다. Pypy3로 제출해야 한다.
Author And Source
이 문제에 관하여(BOJ1780 종이의 개수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehe228/boj1780저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)