boj1780-종이의 개수
문제
문제: https://www.acmicpc.net/problem/1780
내 풀이 (5816ms)
import sys
input = sys.stdin.readline
N = int(input())
paper = [list(map(int, input().split())) for _ in range(N)]
# print(paper)
minus, zero, plus = 0,0,0
def dq9(x ,y, n):
global minus, zero, plus
check = paper[x][y]
for i in range(x, x+n):
for j in range(y, y+n):
if check != paper[i][j]:
dq9(x, y, n//3) # (0,0)
dq9(x, y+n//3, n//3) # (0,1)
dq9(x, y+(n//3)*2, n//3) # (0,2)
dq9(x+n//3, y, n//3) # (1,0)
dq9(x+n//3, y+n//3, n//3) # (1,1)
dq9(x+n//3, y+(n//3)*2, n//3)
dq9(x+(n//3)*2, y, n//3)
dq9(x+(n//3)*2, y+n//3, n//3)
dq9(x+(n//3)*2, y+(n//3)*2, n//3) # (2,2)
return
if check == -1:
minus += 1
return
elif check == 0:
zero += 1
return
else:
plus +=1
return
dq9(0,0,N)
print(minus)
print(zero)
print(plus)
쿼드트리와 같은 풀이, 시작 원소 위치와 종이 크기만 다르게 해서 4가 아닌 9번 호출
다른 풀이 (2956ms)
"""1780 종이의 개수"""
import sys
input = sys.stdin.readline
minus_one, zero, one = 0, 0, 0 # -1 종이의 수, 0 종이의 수, 1 종이의 수
def oneColor(n, y, x):
global minus_one, zero, one
if n == 1: # 종이의 크기가 1칸일 때
if papers[y][x] == "-1":
minus_one += 1
elif papers[y][x] == "0":
zero += 1
else:
one += 1
return
flag = True # 현재 종이가 같은 숫자인지 확인
for j in range(y, y + n):
if not flag:
break
for i in range(x, x + n):
if papers[y][x] != papers[j][i]:
flag = False
break
if flag: # 다 같은 숫자일 때
if papers[y][x] == "-1":
minus_one += 1
elif papers[y][x] == "0":
zero += 1
else:
one += 1
return
else: # 다른 숫자일 때
n //= 3
# 윗 줄
oneColor(n, y, x)
oneColor(n, y, x + n)
oneColor(n, y, x + n * 2)
# 중간 줄
oneColor(n, y + n, x)
oneColor(n, y + n, x + n)
oneColor(n, y + n, x + n * 2)
# 아랫 줄
oneColor(n, y + n * 2, x)
oneColor(n, y + n * 2, x + n)
oneColor(n, y + n * 2, x + n * 2)
num = int(input().rstrip()) # 3의 제곱승으로만 들어옴
papers = [list(input().split()) for _ in range(num)] # 종이의 상태를 받음
oneColor(num, 0, 0)
print(minus_one)
print(zero)
print(one)
종이 크기 1일때 처리,
종이 모두 같은 숫자인지 확인시 1,2,중 for문에서 모두 True, False 체크 후 break
- 출처 : boj kmj951015님 풀이
Author And Source
이 문제에 관하여(boj1780-종이의 개수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dust_potato/boj1780-종이의-개수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)