[백준] 2630 색종이 만들기

📖 문제

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

💻 내 코드

import sys

n=int(sys.stdin.readline())

paper=[]
for _ in range(n):
    paper.append(list(map(int, sys.stdin.readline().split())))

cnt, total=0,0
def find(size, x, y):
    if isSame(size, x, y):
        return

    ns=size//2
    find(ns, x, y)
    find(ns, x, y+ns)
    find(ns, x+ns, y)
    find(ns, x+ns, y+ns)


def isSame(size, x, y):
    global cnt, total
    k=paper[x][y]
    for i in range(x, x+size):
        for j in range(y, y+size):
            if paper[i][j] != k:
                return False
    if k==1:
        cnt+=1
    else:
        total+=1
    return True
find(n, 0, 0)

print(total)
print(cnt)

💡 풀이

• 분할 정복 이용
• size를 2로 나누어 가면서 만약 나눠둔 칸 안이 모두 같다면 True, 아니라면 False를 반환
• 만약 나눈 칸 내부의 수가 모두 1이라면 파란 색종이의 수를 +1 아니라면 하얀 색종이의 수를 +1
• 만약 False를 반환했을 경우 다시 크기를 2로 나누어서 계산

다른 사람 코드 참고해서 새로 짠 코드

import sys

n=int(sys.stdin.readline())

paper=[]
for _ in range(n):
    paper.append(list(map(int, sys.stdin.readline().split())))

w,b=0,0
def find2(size, x, y):
    global w,b
    k=paper[x][y]
    for i in range(x, x+size):
        for j in range(y, y+size):
            if k!=paper[i][j]:
                ns=size//2
                find2(ns, x, y)
                find2(ns, x, y+ns)
                find2(ns, x+ns, y)
                find2(ns, x+ns, y+ns)
                return
    if k==1:
        b+=1
    else:
        w+=1

find2(n,0,0)
print(w)
print(b)

• 함수 내부에서 한번에 같은지 다른지 확인