[백준 / Python] 1780번 종이의 개수

---

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

1780번: 종이의 개수

---

풀이

n = int(input())
paper = [list(map(int, input().split())) for _ in range(n)]
# print(paper)
answer = [0, 0, 0] # -1 0 1
def cntPaper(x, y, m):
    
    cknum = paper[y][x]
    ck = True
    ########### m이 1이면 answer올리고 끝 
    if m == 1:
        if cknum == -1:
            answer[0] += 1
            # print('answer[0]')
        elif cknum == 0:
            answer[1] += 1
            # print('answer[1]')
        elif cknum == 1:
            answer[2] += 1
            # print('answer[2]')
        return
    ## 1이 아니라면 다른지 체크 , 다르면 ck == False 다 같으면 ck == True 
    for i in range(x, x + m):
        if not ck:
            break
            
        for j in range(y, y+m):
            if cknum != paper[j][i]:
                ck = False
                
                break
    cknum = paper[y][x]
    if ck:#색이 같다면 
        if cknum == -1:
            answer[0] += 1
        elif cknum == 0:
            answer[1] += 1
        elif cknum == 1:
            answer[2] += 1
    else: # 색이 다르다면 
        mc = m // 3
        cntPaper(x, y, mc) # 1
        cntPaper(x, y+ mc, mc) # 2
        cntPaper(x, y+ mc+ mc, mc) # 3
        
        cntPaper(x+ mc, y, mc) # 4 
        cntPaper(x+ mc, y+ mc, mc) # 5 
        cntPaper(x+ mc, y+ mc+ mc, mc) # 6
        
        cntPaper(x+ mc+ mc, y, mc)# 7
        cntPaper(x+ mc+ mc, y+ mc, mc) # 8 
        cntPaper(x+ mc+ mc, y+ mc+ mc, mc) # 9
        return

cntPaper(0, 0, n)

for i in answer:
    print(i)

분할정복 풀이이다. 

 

(x좌표, y좌표, 정사각형의 길이)를 파라미터로 하는 함수를 만들고 

함수가 보고있는 종이의 값이 모두 같다면 그 값의 카운트를 +1 한다. 

종이의 값이 하나라도 다르다면 보고있는 종이를 9개로 분할하는 풀이이다.