색종이 만들기 파이썬

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

그동안 백준을 너무 멀리했다

분할정복의 첫번째 문제다

나는 분할정복이 정확히 무엇을 의미하는지 잘 모른다

그러나 이 색종이 만들기라는 문제 일단 분할정복이 뭔지몰라도 

적어도 접근조차는 할수있는 문제라는 생각이든다

 

먼저 문제에서 소개한방식으로 구현을 할경우

해당영역이 모두 0또는 1인지검사 => 모두 같은색으로 칠해져있는경우 유지 아니면 영역 4분할인데

 

이경우 계속 검사하게되는 부분이 생긴다 모두 같은 수로 차있는지 말이다

하지만 이방법말고 다른방법이 지금 내 졸린뇌에서 떠오르지가 않는다 

 

일단 이방법으로 구현해보고

시간초과가 나면 다른방법을 생각해보자

-------------------221008--------------

결론부터 말하자면 첫번째 제출에 통과했다

다른사람들이 작성한 코드와의 실행속도를 비교해보았을때 빠르다고 볼수없는 속도인것을 확인했다

 

재귀함수를 이용해 풀었다

색깔이 통일되어있지않다면 색깔이 통일된 사각형이 나올때까지 4등분을 한다

어려운문제인줄알았는데 너무쉽게 풀어버린것같다

 

아래는 코드다

white=0
blue=0

la=[]
for i in range(int(input())):
    a=list(map(int,input().split()))
    la.append(a)

def sje(paper):
    global white
    global blue
    fc=paper[0][0]
    
    lena=len(paper)
    cnt=0
    for i in range(lena):
        for j in range(lena):
            if paper[i][j]!=fc: 
                cnt+=1
                break
        if cnt!=0:
            break

    if cnt==0:
        if fc==0:
            white+=1
        else:
            blue+=1
    
    else:
        la2=[]
        for i in range(lena//2):
                la2.append(paper[i][:lena//2])
        la3=[]
        for i in range(lena//2):
            la3.append(paper[i][lena//2:])
        la4=[]
        for i in range(lena//2,lena):
                la4.append(paper[i][:lena//2])
        la5=[]
        for i in range(lena//2,lena):
            la5.append(paper[i][lena//2:])
        
        sje(la2)
        sje(la3)
        sje(la4)
        sje(la5)

sje(la)
print(white)        
print(blue)