2022.02.21 [백준] (python 파이썬) 종이의 개수

 

 

 

 

 

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

1780번: 종이의 개수

---

풀이

이 문제는 분할 정복, 재귀함수 문제이다.

(5~7) n이 1이면 더 이상 분할할 수 없기 때문에 해당 인덱스값의 카운트 증가

        (ans배열안에 arr+1을 해준 이유는 배열의 인덱스는 0부터 시작하기 때문에 -1을 처리하기 위해 +1을 해서 저장           함.)

(9~16) 우선 해당 종이의 범위에 숫자가 모두 같은지 확인한다.

(17~18) 같으면 해당 종이의 첫인덱스값을 ans배열에 저장한다.

(19~23) 해당 종이안에 값이 다르면 해당 종이를 9등분 해주고 분할된 종이를 재귀함수를 이용하여 다시 확인해줌.

 

n=int(input())
arr=[list(map(int, input().split())) for _ in range(n)]
ans=[0]*3
def Cal(n,x,y):
    if n==1:
        ans[arr[x][y]+1]+=1
        return
 
    check=True
    for i in range(x,x+n):
        for j in range(y,y+n):
            if arr[x][y]!=arr[i][j]:
                check=False
                break
        if not check:
            break
    if check:
        ans[arr[x][y]+1]+=1
    else:
        a=n//3
        for i in range(3):
            for j in range(3):
                Cal(a,x+a*i,y+a*j)
Cal(n,0,0)
for i in ans:
    print(i)