[Python]분할정복 백준 1780

   문제

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

앞의 색종이 문제와 동일하게 풀어냈다.

코드를 짜는데 있어서 달라진점은 등분을 나누기 위해 for문을 사용하였다.

 이후 3등분이 아니라 5등분 10등분이여도 같이 적용할수있도록...

import sys
 
 
n=int(sys.stdin.readline())
 
#-1 0 1
paper=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]
 
 
result=0#-1
result0=0#0
result1=0#1
 
 
 
def cut(x,y,n):
    global result,result0,result1
    check=paper[x][y]
    for i in range(x,x+n):
        for j in range(y,y+n):
            if check!=paper[i][j]:
                #9등분하기
                for a in range(3):
                    for b in range(3):
                        cut(x+n//3*a,y+n//3*b,n//3)
                return
 
    if check==-1:
        result+=1
    elif check==0:
        result0+=1
    elif check==1:
        result1+=1
 
 
cut(0,0,n)
print(result)
print(result0)
print(result1)

속도가 좀 느리다...

반복문에서 반복하지 않아도 되는 n//3같은 경우 변수로 바꾸어주고

배열을 검사하는데 있어 짤라서 검사하는경우 속도가 빨라질거같다.

다음에 기회가 생긴다면 최적화 시켜봐야겠다.