GitHub

https://github.com/Choidongjun0830

파이썬 알고리즘 문제 풀이

Baekjoon Online Judge 1780번 파이썬. 분할 정복.

gogi masidda 2022. 12. 27. 17:47

문제 링크
https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수

www.acmicpc.net


2630번 문제와 유사하다.
다른 점은 9개로 자르는 것이기 때문에 ‘N//3’을 하고, 재귀함수의 시작점. x,y가 9개 있다는 것이다.

정답 코드

N = int(input())
matrix = [list(map(int,input().split()))for i in range(N)]

result = []
def solution(x,y,N):
  number = matrix[x][y]
  for i in range(x,x+N):
    for j in range(y,y+N):
      if number != matrix[i][j]:
        n = N//3
        solution(x,y,n)
        solution(x,y+n,n)
        solution(x,y+2*n,n)
        solution(x+n,y,n)
        solution(x+n,y+n,n)
        solution(x+n,y+2*n,n)
        solution(x+2*n,y,n)
        solution(x+2*n,y+n,n)
        solution(x+2*n,y+2*n,n)
        return
  if number == -1:
    result.append(-1)
  elif number == 0:
    result.append(0)
  else:
    result.append(1)

solution(0,0,N)
print(result.count(-1))
print(result.count(0))
print(result.count(1))
728x90